La Búsqueda Binaria, también denominada búsqueda Dicotómica, es un algoritmo que busca un valor determinado en un vector ordenado según la siguiente operatoria:
Compara el valor del elemento que está en la posición media del vector con el valor buscado, si no son iguales, la mitad en la cual el valor no está es eliminada y la búsqueda continua en la mitad restante, realizando la misma operación hasta que el valor se encuentre o no.
La primera vez que se habló de búsqueda binaria fue por John William Mauchly en 1.946, después en 1.960 Derrick Henry Lehmer describió el algoritmo y a partir de aquí surgen distintas versiones. Una de las más utilizadas fue la publicada por L. Jon Bentley en 1.986, que sirvió de controversia cuando Joshua Bloch descubrió, en 2.006, que el algoritmo que él había escrito, basado en la publicación de Bentley, y para las librerías de Java, contenía un “bug”, error que estaba presente en otros lenguajes.
La controversia era más “filosófica” que otra cosa, se utilizó una frase de Edsger W. Dijkstra:
“We could, for instance, begin with cleaning up our language by no longer calling a bug a bug but by calling it an error. It is much more honest because it squarely puts the blame where it belongs, viz. with the programmer who made the error.”
Digamos que Dijkstra tiene razón, pero algo que no debemos olvidar es:
“Cuando un programador comete un error, pronto o tarde aparecerá y no podrá discutirlo. En otras profesiones es fácimente ocultable, esta profesión en ocasiones es muy ingrata”.
Un ejemplo:
Los valores límite de la variable son inferior(0) y superior(40000000) y el punto medio entre ellos es mitad, hacemos lo siguiente:
- Preguntamos si el valor está entre inferior y mitad
- Si nos dice que sí, descartamos la parte del vector entre las posiciones mitad y superior. En caso contrario entre inferior y mitad.
- Calculamos el punto medio del vector que queda y repetimos la operación hasta llegar al valor.
El coste de este sistema es de log2(n), donde n es el número de valores entre inferior y superior.
