Algoritmos Avanzados en Python

Implementación de búsqueda binaria

El catálogo de PyShop tiene 100,000 SKUs ordenados, del 1000107 al 9999882. Para saber si un SKU existe, una búsqueda lineal recorre la lista desde el principio: sobre 1000 SKUs elegidos al azar hace 50,526 comparaciones de media. La búsqueda binaria hace 15.7, y nunca más de 17. El notebook busqueda-binaria construye esa diferencia paso a paso, contando comparaciones en lugar de medir segundos; esta lección es su guía.

1. Lineal contra binaria, con contador

La búsqueda binaria solo funciona sobre datos ordenados. Compara contra el elemento del medio del intervalo y descarta la mitad donde el objetivo no puede estar. Cada comparación parte el intervalo en dos, así que el peor caso es $\lceil \log_2(n+1) \rceil$ comparaciones:

def binaria(xs, x):
    lo, hi, comps = 0, len(xs) - 1, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        comps += 1
        if xs[mid] == x:
            return mid, comps
        if xs[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, comps

cat = generar_catalogo()
print(binaria(cat, 1234567))   # (-1, 16)

Para un SKU que no existe, como el 1234567, la lineal hace las 100,000 comparaciones y la binaria 16. Al crecer el catálogo la brecha se abre: con 1,000 elementos el peor caso es 1,000 contra 10; con un millón, 1,000,000 contra 20; con mil millones, 1,000,000,000 contra 30. Multiplicar los datos por mil le suma solo 10 comparaciones a la binaria.

2. Versión iterativa y recursiva

El notebook también escribe la versión recursiva: la función recibe lo y hi y se llama a sí misma sobre la mitad que sobrevive. Hace las mismas comparaciones, pero su profundidad de recursión crece con $\log_2 n$; con 100,000 elementos son como mucho 18 niveles (17 comparaciones más la llamada que encuentra el intervalo vacío), muy lejos del límite de 1000 que Python trae por defecto. En la práctica se prefiere la iterativa: no crea marcos de llamada y es igual de clara.

3. El invariante y los errores de uno

La binaria es famosa por fallar en detalles. La manera de escribirla bien es fijar un invariante: «si x está en la lista, está entre lo y hi, ambos incluidos». De ahí salen todas las decisiones:

• hi empieza en len(xs) - 1, no en len(xs), porque el intervalo es cerrado.
• El ciclo usa lo <= hi: con < se salta el caso de un solo elemento.
• Se avanza con mid + 1 y mid - 1: si se asigna lo = mid, el ciclo puede no terminar nunca.

El notebook prueba la función contra la lineal en miles de casos, incluidos el primer y el último SKU y valores fuera de rango. Esa comparación automática atrapa los errores de uno que la lectura no ve.

4. bisect_left y bisect_right

El módulo bisect de la biblioteca estándar implementa la búsqueda binaria en C. No devuelve «encontrado o no», sino un punto de inserción: dónde habría que insertar el valor para mantener el orden. Con valores repetidos, bisect_left da la posición antes del primero y bisect_right la posición después del último:

from bisect import bisect_left, bisect_right
import random

precios = sorted(random.Random(3).choices(range(100, 2000, 50), k=200))
print(bisect_left(precios, 450), bisect_right(precios, 450))   # 31 34
print(bisect_right(precios, 800) - bisect_left(precios, 500))  # 42

La diferencia 34 − 31 = 3 dice cuántas veces aparece 450 sin recorrer la lista. Con la misma idea se cuentan rangos: hay 42 productos con precio entre 500 y 800, incluidos los extremos. Desde Python 3.10, las funciones de bisect aceptan key= para buscar en listas de registros.

5. Búsqueda binaria sobre la respuesta

La binaria no solo busca en listas: busca en cualquier rango donde una condición pasa de falsa a verdadera una sola vez. Los 20 paquetes del día (124 kg en total, el más pesado de 13 kg) se entregan en el orden en que llegaron. ¿Qué capacidad mínima necesita la camioneta para hacerlo en 3 viajes? Si una capacidad alcanza, cualquier capacidad mayor también; esa monotonía permite buscar entre 13 y 124:

def viajes(cap, pesos):
    n, carga = 1, 0
    for w in pesos:
        if carga + w > cap:
            n, carga = n + 1, 0
        carga += w
    return n

pesos = [p[1] for p in generar_paquetes()]
lo, hi = max(pesos), sum(pesos)
while lo < hi:
    mid = (lo + hi) // 2
    lo, hi = (lo, mid) if viajes(mid, pesos) <= 3 else (mid + 1, hi)
print(lo)   # 44

La respuesta es 44 kg en 7 pasos; para 5 viajes, 30 kg, también en 7. Probar las 112 capacidades una por una costaría hasta 112 simulaciones.

Trampas comunes

• Buscar en datos sin ordenar. La binaria devuelve basura sin avisar; ordenar cuesta $O(n \log n)$ y solo conviene si se busca muchas veces.
• Usar in en una lista ordenada. x in lista es lineal aunque la lista esté ordenada.
• Confundir el punto de inserción con «encontrado». Tras bisect_left hay que verificar que i < len(xs) y xs[i] == x.
• Condición no monótona en la búsqueda sobre la respuesta: si alcanzar con 40 no implica alcanzar con 41, el método no aplica.

Cierre

Al terminar el notebook, toma cualquier pregunta del tipo «¿cuál es el mínimo valor que cumple…?» y pregúntate si la condición es monótona. Si lo es, la respuesta está a $\log_2$ del tamaño del rango.