Título: [C] Búsqueda binaria recursiva Publicado por: BatchianoISpyxolo en 29 Octubre 2012, 18:54 pm Este pequeñito aporte va dedicado especialmente a aquellos que comienzan recién en la programación :D
Prerrequisitos (?) → Vectores → Saber qué es y cómo se lleva a cabo la búsqueda binaria Adjunto el código del algoritmo no recursivo (Por: Rodrigo Burgos Domínguez.): http://algorithmmx.blogspot.com.es/2011/11/algoritmo-de-busqueda-binaria.html Código
Teniendo en cuenta que ya sabemos la lógica que sigue este algoritmo y su implementación arriba expuesta, vamos a pensar en hacerlo de forma recursiva, es decir, que la misma función vaya reduciendo el tamaño (N) del problema a un caso base, de tal manera, al conocer la solución del caso base, va a poder dar solución a cualquier problema de tamaño N. Entonces el código sería el siguiente: (utilizo int casting para no usar la librería math.h) Código
Explicación general: La premisa que tenemos es que nosotros tenemos que buscar un elemento x en un vector v de tamaño N que está previamente ordenado. Teniendo eso en cuenta podemos afirmar que cualquier subvector w de v de tamaño [0..N] también está ordenado. Pues teniendo eso en cuenta vamos reduciendo el tamaño del problema (N) a la mitad en cada llamada recursiva. ¿Por qué? Porque si x no es el elemento medio del vector v de tamaño N, entonces verificamos si es menor o mayor que él. Si es menor, buscamos en el subvector de tamaño N/2 izquierdo, sino en el derecho. Como véis, en este caso, el algoritmo se pasa de forma cíclica a forma recursiva casi sin pensar. ¿Por qué? Estamos ante una Tail Recursive Function (la autollamada es lo último que se hace) y podemos pensar en definitiva que estamos ejecutando un ciclo simplemente. Podría aquí estar escribiendo horas y horas sobre algoritmos de búsqueda y ordenación pero no es plan xD Decir simplemente que hay tener en cuenta que el vector en el que vayamos a buscar un elemento, debe estar previamente ordenado. En este momento os preguntaréis: ¿Qué me conviene más, buscar directamente en un vector con la búsqueda lineal o es mejor ordenarlo previamente (quicksort) y luego aplicar búsqueda binaria? Bueno eso ya son temas de complejidad algorítmica y haciendo un pequeño estudio se puede sacar conclusiones. Decir también que hay estructuras de datos eficientes para la búsqueda como lo son por ejemplo las Tablas Hash o los Árboles Binarios de Búsqueda, ABB (variante AVL), por ejemplo. Bueno con esto y un bizcocho me despido. ¡Saludos! Todos los comentarios serán bien recibidos :) Título: Re: [C] Búsqueda binaria recursiva Publicado por: Stakewinner00 en 29 Octubre 2012, 22:59 pm Hoy pase a releer las normas y me vi que casi nadie las cumplia al 100%.
Felicidades eres de los pocos que cumplen las normas creo ;-). Título: Re: [C] Búsqueda binaria recursiva Publicado por: BatchianoISpyxolo en 29 Octubre 2012, 23:06 pm Hoy pase a releer las normas y me vi que casi nadie las cumplia al 100%. Felicidades eres de los pocos que cumplen las normas creo ;-). Será eso de la experiencia... jaja Título: Re: [C] Búsqueda binaria recursiva Publicado por: flony en 29 Octubre 2012, 23:08 pm para leer ;-)
|