Binary Search

La búsqueda binaria compara contra el elemento central de un array ordenado y reduce el rango a la mitad cada vez, localizando un objetivo en O(log n); es el algoritmo de búsqueda eficiente fundamental.

Propósito

Localizar elementos de forma eficiente en datos ordenados, aplicando complejidad logarítmica a la búsqueda.

Mecanismo

Se mantiene el intervalo [lo, hi] con mid=(lo+hi)/2; se compara mid con el objetivo: se devuelve si es igual, se busca la mitad derecha si es menor, la izquierda si es mayor. El intervalo se reduce a la mitad en cada paso, dando O(log n). Estar ordenado es un requisito previo. Variantes: cota inferior, cota superior, punto de inserción.

Casos de uso

Búsqueda en arrays ordenados
Índices B+ tree de bases de datos
Bisect en control de versiones
Búsqueda de ceros de funciones (bisección)

Ejemplos

entrada
```
Search 5 in [1,3,5,7,9]
```
Output
```
Index 2
```
2 comparisons

Errores comunes

lo+hi integer overflow: Use lo+(hi-lo)/2

Términos relacionados

Sorting Algorithm

Los algoritmos de ordenación disponen los elementos en orden —quicksort, merge sort y heapsort son comunes— con complejidades que van de O(n log n) a O(n²).

La notación O grande describe el límite superior asintótico de una función, usada para analizar la complejidad temporal/espacial de los algoritmos ignorando constantes y términos de orden inferior.

Una tabla hash mapea claves a un array de cubos mediante una función hash, ofreciendo búsqueda/inserción/borrado promedio O(1); es una de las estructuras de datos más usadas.

References