Búsqueda binaria encuentra un objetivo en un arreglo ordenado dividiendo repetidamente el rango de búsqueda a la mitad. Cada comparación elimina la mitad de los elementos restantes, dando una complejidad de O(log n).
Mira el elemento del medio. Si es igual al objetivo, listo. Si el objetivo es menor, busca en la mitad izquierda; si es mayor, busca en la mitad derecha. Repite hasta encontrarlo o hasta que el rango esté vacío.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2 # middle index
if arr[mid] == target:
return mid # found it
elif arr[mid] < target:
lo = mid + 1 # discard left half
else:
hi = mid - 1 # discard right half
return -1 # not present
binary_search([1, 3, 5, 7, 9], 7) # -> 3
Search 7 in [1,3,5,7,9]
lo=0 hi=4 mid=2 -> 5 < 7 => lo=3
lo=3 hi=4 mid=3 -> 7 == 7 => return 3
La entrada debe estar ordenada — de lo contrario los resultados no tienen sentido. Ten cuidado con errores off-by-one en lo/hi y overflow de enteros en algunos lenguajes (usa lo + (hi-lo)//2).
Dividir el espacio de búsqueda a la mitad convierte una búsqueda en un arreglo de un millón de elementos en ~20 comparaciones.
El patrón divide-y-conquista detrás de esto reaparece en árboles, bases de datos e incontables problemas de entrevistas.
Conocer su único requisito hard — entrada ordenada — te mantiene alejado de un error clásico y sutil.