En 1946, John Mauchly mencionó por primera vez la búsqueda binaria como parte de Moore School Lectures, Las siguientes publicaciones mencionaban que la búsqueda binaria sólo funcionaba en arreglos cuya longitud fuese de uno menos que una potencia de dos hasta 1960, cuando Derrick Henry Lehmer público un algoritmo de búsqueda binaria que funcionaba en todos los arreglos ordenados.
En 1962, Hermann Bottenbruch presentó en ALGOL 60 una implementación del algoritmo de búsqueda binaria en el cual colocaba la comparación de igualdad en el final del algoritmo, incrementando el número promedio de iteraciones por uno, pero reduciendo a uno el número de comparaciones por iteración. La búsqueda binaria uniforme fue presentada a Donald Knuth en 1971 por A. K. Chandra de la universidad de Stanford y publicado en el libro de Knuth: The Art of Computer Programming.
¿Qué es búsqueda binaria?
Es un algoritmo eficiente para encontrar un elemento en una lista ordenada de elementos. Funciona al dividir repetidamente a la mitad la porción de la lista que podría contener al elemento, hasta reducir las ubicaciones posibles a solo una.
¿Cómo funciona la búsqueda binaria?
-
1. Se declaran los índices superior e inferior. El inferior en 0 y el superior con el tamaño del arreglo menos 1.
-
2. Se calcula el centro del arreglo con la siguiente fórmula: centro = (superior + inferior) / 2
-
3. Verificamos si el arreglo en la posición centro es igual al dato que buscamos. Si es igual significa que encontramos el dato y retornamos el centro.
-
4. Si son diferentes verificamos si el arreglo en la posición centro es mayor al dato que queremos buscar. Si es mayor actualizamos superior: superior = centro - 1, si no actualizamos inferior: inferior = centro + 1.
-
5. Volvemos al paso 2, hasta encontrar el dato que buscamos.
Características
Uno de los algoritmos de búsqueda más eficiente que existe en la estructura de datos es la búsqueda binaria, las características para poder implementar este algoritmo son las siguientes:
-
Los datos deben estar contenido en un estructura de datos tipo vector
-
Los datos del vector deben estar ordenados
Ventajas de la búsqueda binaria
-
La búsqueda binaria proporciona un medio para reducir el tiempo requerido para buscar en una lista.
-
Es más rápido por su recursividad, su mayor ventaja es con los archivos extensos.
Desventajas de la búsqueda binaria
-
El archivo debe estar ordenado y el almacenamiento de un archivo ordenado suele plantear problemas en las inserciones y eliminaciones de elementos.
-
No revisa todos los elementos del archivo, requiere que todos los elementos estén ordenados
Referencias
Búsqueda binaria (artículo) | Algoritmos. (s. f.). Khan Academy. https://es.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-search
5.4. La búsqueda binaria — Solución de problemas con algoritmos y estructuras de datos. (s. f.). Runestone.academy. https://runestone.academy/runestone/static/pythoned/SortSearch/LaBusquedaBinaria.html
Aguilar, L. J., Martínez, I. Z., coaut, Z. M. I., Sáncjez, A. V., & Vieyra, G. Q. (1998). Estructura de datos. McGraw-Hill Education.