¿Quién inventó el algoritmo de búsqueda binaria?
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.
¿Cómo se realiza la búsqueda binaria?
Cuando realizamos la búsqueda binaria, buscamos en una mitad y descartamos la otra mitad, reduciendo el tamaño del array a la mitad cada vez. La expresión para la complejidad del tiempo viene dada por la recurrencia.
¿Cómo se clasifican los algoritmos de búsqueda?
El tipo de búsqueda se puede clasificar como interna o externa, según el lugar en el que esté almacenada la información (en memoria o en dispositivos externos). Todos los algoritmos de búsqueda tienen dos finalidades:
¿Cuál es la mejor manera de comparar una búsqueda binaria o lineal?
Sin embargo, es más eficiente incluso al considerar el costo del ordenamiento. Por ejemplo, un arreglo de 10 elementos haría como máximo 4 comparaciones en el caso de una búsqueda binaria contra 10 en una búsqueda lineal, lo que no es una gran mejora.
¿Cuál es el peor caso en la búsqueda binaria?
Sin embargo, para un arreglo con 1,000,000 elementos el peor caso en la búsqueda binaria es solamente 20 comparaciones. ¡Esa es una gran mejora en comparación a la búsqueda lineal!.
¿Cómo calcular el rendimiento de la búsqueda binaria?
El rendimiento de la búsqueda binaria puede ser analizada reduciendo el algoritmo a un árbol binario de búsqueda, donde la raíz es el elemento en el medio del arreglo, el elemento en el medio de la primera parte del arreglo es el hijo izquierdo de la raíz y el elemento en el medio de la segunda parte es el hijo derecho de la raíz.
