Búsqueda binaria

Teoria

Este algoritmo se usa para buscar elementos en un conjunto de datos ordenados tipo lista.

La idea es la siguiente, usando el principio divide y vencerás ir limitando el rango de búsqueda, como cuando se busca una página de un libro, se abre el libro en una página al azar, si está más adelante pues pasamos un grupo de páginas así delante de lo contrario nos devolvemos, reduciendo el rango de búsqueda hasta llegar a la página buscada.
Se compara el elemento a buscar, con un elemento central de la lista, si este elemento central es mayor que el del elemento buscado, se toma el intervalo inferior (del inicio a la mitad de la lista, en caso contrario se toma la parte de superior (que va desde el elemento de la mitad hasta el final); en los dos casos, se repite el procedimiento en la parte del lista seleccionada. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en toda la lista.

Caso estudio

Buscando en su ordenada colección de comics Alexander que hallar la edición 84 de “The Walking Dead”, lo haría de la siguiente manera.

1. Se divide la lista en dos y se ubica el elemento de la mitad, en este caso TWD 77.

2. Lo comparamos con el que queremos encontrar que es el 84, el elemento referencia (77) es menor, entonces se toma la parte “superior” de la lista.

3. Ahora se repite el procedimiento con la nueva lista, se toma el elemento de la mitad.

4. Lo comparamos con el que queremos encontrar que es el 84, el elemento referencia (99) es mayor, entonces se toma la parte “inferior” de la lista.

5. Ahora se repite el procedimiento con la nueva lista, se toma el elemento de la mitad.

6. Lo comparamos con el que queremos encontrar que es el 84, el elemento referencia (84) es mayor, como son igual quiere decir que ya encontramos el elemento que estábamos buscando y está en la posición 7.

Algoritmo

1. Se busca el elemento de la mitad de la lista.
2. Se compara con el elemento que se está buscando.
a. Si el elemento de la mitad es mayor, se toma la parte de inferior de la lista (del primer elemento al de la mitad) vuelve al paso 1 pero con esta nueva sublista.
b. Si el elemento de la mitad es menor, se toma la parte de superior de la lista (del elemento de la mitad hay último elemento) vuelve al paso 1 pero con esta nueva sublista.
c. Si el elemento de la mitad es igual al elemento que estamos buscando se concluye la búsqueda exitosamente (fin).
d. Es el último elemento de la lista y no es igual al que se está buscando, el elemento no está en la lista (fin).