Búsqueda binaria explicada: cómo funciona, código y complejidad

Qué problema resuelve la búsqueda binaria

La búsqueda lineal revisa los elementos uno por uno y necesita hasta n comparaciones. Si los datos están ordenados, se puede hacer mucho mejor: compara el objetivo con el elemento central y sabrás de inmediato qué mitad conservar. Es la misma idea que buscar una palabra en un diccionario en papel.

La búsqueda binaria también funciona con cualquier cosa monótona, no solo con arreglos. Si una condición de sí/no es falsa para todos los valores pequeños y verdadera para todos los grandes, la búsqueda binaria encuentra la frontera. Esto se llama búsqueda binaria sobre la respuesta.

Ejemplo resuelto, paso a paso

Busca 23 en la lista ordenada [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (índices del 0 al 9). Mantén dos índices, lo y hi, que delimitan el rango que aún falta por comprobar.

Tres comparaciones en lugar de seis en un recorrido lineal. Para una lista de un millón de elementos, la búsqueda binaria necesita como máximo 20.

Implementación en Python

La versión iterativa de abajo usa un rango cerrado [lo, hi]: ambos extremos siguen siendo candidatos. El bucle se ejecuta mientras el rango no esté vacío.

def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            lo = mid + 1          # target is in the right half
        else:
            hi = mid - 1          # target is in the left half
    return -1                     # not found
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(data, 23))   # 5
print(binary_search(data, 7))    # -1

En código Python real, usa el módulo bisect de la biblioteca estándar. bisect_left devuelve la posición más a la izquierda donde se podría insertar el objetivo manteniendo la lista ordenada, lo que además indica si está presente.

from bisect import bisect_left, bisect_right, insort
data = [1, 3, 3, 3, 7, 9]
i = bisect_left(data, 3)
print(i, bisect_right(data, 3))   # 1 4  (3 occupies indexes 1..3)
print(i < len(data) and data[i] == 3)   # True: 3 is present
print(bisect_left(data, 5))       # 4: insertion point for 5
insort(data, 5)
print(data)                       # [1, 3, 3, 3, 5, 7, 9]

Complejidad temporal y espacial

Variantes: primero, último y búsqueda binaria sobre la respuesta

Muchos problemas no preguntan si existe un valor, sino dónde está una frontera: el primer índice con un valor mayor o igual que x, la última aparición de x o el menor número que cumple una condición. Usa un rango semiabierto [lo, hi) y nunca termines antes de tiempo.

def first_true(lo, hi, ok):
    """Smallest x in [lo, hi) with ok(x) True, or hi if none.
    ok must be False...False True...True over the range."""
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid          # mid may be the answer, keep it
        else:
            lo = mid + 1      # mid is too small
    return lo
data = [1, 3, 3, 3, 7, 9]
print(first_true(0, len(data), lambda i: data[i] >= 3))   # 1
# Integer square root of 200: largest x with x*x <= 200
print(first_true(0, 201, lambda x: x * x > 200) - 1)      # 14

• Cota inferior (primer índice con valor ≥ x): bisect_left.
• Cota superior (primer índice con valor > x): bisect_right.
• Número de apariciones de x en una lista ordenada: bisect_right(a, x) - bisect_left(a, x).
• Buscar en un arreglo ordenado rotado, encontrar picos y minimizar un máximo (por ejemplo, la menor capacidad que permite enviar todos los paquetes en D días) son variantes clásicas de entrevista.

Errores comunes

• Mezclar convenciones de rango. Con un rango cerrado usa lo <= hi y hi = mid - 1; con un rango semiabierto usa lo < hi y hi = mid. Mezclarlas provoca bucles infinitos o elementos omitidos.
• Escribir lo = mid en lugar de lo = mid + 1. Cuando hi = lo + 1, mid es igual a lo y el bucle nunca termina.
• Ejecutar la búsqueda binaria sobre datos sin ordenar. Devuelve respuestas incorrectas sin ningún error.
• Desbordamiento de enteros en (lo + hi) / 2 en lenguajes con enteros de tamaño fijo como Java, C y C++. Usa lo + (hi - lo) / 2. Los enteros de Python no se desbordan, así que (lo + hi) // 2 es seguro.
• Devolver la primera coincidencia encontrada cuando la tarea pide la primera aparición entre duplicados.

Cuándo usar la búsqueda binaria

Entre sus usos reales están los índices de bases de datos y sistemas de archivos (los árboles B generalizan la idea), git bisect para encontrar el commit que introdujo un error, la búsqueda de un valor en una tabla ordenada de rangos, como bloques de IP, y muchos problemas numéricos en los que se busca un umbral.