La búsqueda binaria es un algoritmo de búsqueda eficiente que se utiliza para encontrar un elemento en una lista ordenada.
El principio fundamental de la búsqueda binaria es dividir repetidamente el espacio de búsqueda en dos mitades.
Reduciendo el número de comparaciones necesarias para encontrar el elemento deseado.
Es uno de los algoritmos más comunes en la informática.
Tanto por su simplicidad como por su eficiencia.
Funcionamiento de la búsqueda binaria
El algoritmo sigue un proceso iterativo o recursivo para buscar el elemento en una lista ordenada.
División en mitades
Se toma el elemento central de la lista. Si el valor del elemento buscado es menor que el valor central.
Entonces el algoritmo continúa buscando en la mitad izquierda de la lista.
Si el valor es mayor, se busca en la mitad derecha.
Comparación
Se compara el valor del elemento central con el valor buscado.
Si el valor buscado coincide con el elemento central, el algoritmo termina.
Si no coincide, se descarta la mitad de la lista donde no puede estar el valor.
Reduciendo el tamaño del espacio de búsqueda a la mitad.
Repetición
Este proceso se repite hasta que;
Se encuentra el valor buscado o la lista restante tiene longitud cero.
Significa que el valor no está presente en la lista.
En la lista ordenada [1, 3, 5, 7, 9, 11] queremos encontrar el número 7.
El elemento medio es 5. Como 7 > 5, descartamos la mitad izquierda de la lista.
Ahora la búsqueda se limita a la lista [7, 9, 11], donde el nuevo valor medio es 9. Como 7 < 9, descartamos la mitad derecha.
Queda solo el valor 7, que es el que estamos buscando. El algoritmo termina.
Ventajas
Eficiencia
La búsqueda binaria es muy eficiente en listas grandes.
Reduce el número de comparaciones necesarias para encontrar el elemento.
Tiene una complejidad de tiempo O(log n).
Significa que el tiempo de ejecución crece logarítmicamente con el tamaño de la lista.
Comparado con una búsqueda lineal que tiene complejidad O(n)).
Es mucho más rápido en grandes conjuntos de datos.
Aplicabilidad
Funciona bien con cualquier estructura de datos ordenada, como arrays o listas ordenadas.
Limitaciones
Lista ordenada
La búsqueda binaria solo funciona en listas previamente ordenadas.
Si la lista no está ordenada, primero es necesario ordenarla.
Puede llevar tiempo adicional.
Variantes
Búsqueda binaria recursiva
La implementación de búsqueda binaria puede ser recursiva.
Donde el algoritmo se llama a sí mismo en las mitades correspondientes.
Búsqueda binaria iterativa
También puede implementarse de manera iterativa.
Utilizando un bucle para evitar la sobrecarga de llamadas recursivas.
Aplicaciones
Sistemas de bases de datos
Para búsquedas eficientes en grandes cantidades de datos.
Motores de búsqueda
Para la indexación de datos y recuperación de información.
Algoritmos de optimización
Como en la búsqueda de la raíz en ecuaciones o encontrar un valor en una función monotónica.
La búsqueda binaria es una técnica fundamental en el campo de la inteligencia artificial y la ciencia de la computación.
Debido a su eficiencia en la búsqueda de elementos.
En grandes conjuntos de datos ordenados.
