BÚSQUEDA BINARIA

Para entender más fácilmente este algoritmo, póngamos un ejemplo. Imagina que deseas encontrar el número de teléfono de algún amigo en el directorio telefónico. Por supuesto, lo único que sabes es el nombre de tu amigo y afortunadamente, el directorio telefónico está ordenado alfabéticamente. Una forma sencilla de encontrar el teléfono es como sigue. Compara la primera entrada del directorio con el nombre de tu amigo, si son iguales ya acabaste, si no compara la segunda entrada del directorio con el nombre de tu amigo, si son iguales ya acabaste, si no compara la tercera entrada y así sucesivamente... Esto funciona muy bien si el directorio tiene muy pocas entradas, pero si tiene muchas resulta bastante lento.

Una forma mejor es como sigue: Abre el directorio a la mitad y compara la entrada que veas con el nombre de tu amigo. Si son iguales ya acabaste. ¿Qué pasa si no son iguales? Una de dos: o bien el nombre de tu amigo está antes del que viste, o bien está después. En cualquier caso, has reducido la tarea de encontrar a tu amigo en todo el directorio a encontrarlo en una de sus mitades. Es decir, has dividido la tarea en dos. Por supuesto, el método continúa de la misma forma con la mitad restante, hasta que finalmente obtengas una sección del directorio que contiene solamente una entrada. En ese momento, puede ser que esa entrada corresponda al nombre de tu amigo, o que tu amigo no estuviera en el directorio.

Para simplificar, supongamos que la lista contiene números en lugar de nombres y que los números están ordenados de forma ascendente. Llamemos N a la cantidad de números, L1, L2, ..., LN a los miembros de la lista, y X al número que estamos buscando. También llamemos IZQ al índice izquierdo, DER al índice derecho y MED al punto medio de la parte de la lista que aún estamos considerando. Al principio IZQ = 1 y DER = N. Entonces, podemos ver que el siguiente algoritmo funciona como queremos:

Binaria (IZQ, DER)
Comienza

Si IZQ < DER entonces

MED = (IZQ + DER)/2

Si LMED < X entonces

Binaria(MED, DER)

Si no entonces

Binaria(IZQ, MED)

Si no entonces si LIZQ = X

Imprime "Encontrado en la posición" IZQ

Si no entonces

Imprime "El elemento buscado no está"

Termina

Ejercicios:

Tomando como base este algoritmo, desarrolla uno e impleméntalo para posteriormente determinar su eficiencia. Fíjate en el número de veces que se llama a la función recursiva para determinar adecuadamente los valores de a, b y k.

Demuestre que la búsqueda binaria es óptima para todo algoritmo de búsqueda que sólo realice comparaciones.