Búsqueda binaria

La idea

Si un arreglo está ordenado, buscar en él no exige recorrerlo. La búsqueda binaria mantiene un intervalo de candidatos [lo, hi], mira el elemento central en la posición mid = lo + ⌊(hi − lo)/2⌋ y compara con el objetivo x. Si coincide, terminó; si a[mid] < x, el objetivo solo puede estar a la derecha y hace lo = mid + 1; si a[mid] > x, solo puede estar a la izquierda y hace hi = mid − 1. Cada comparación descarta la mitad de lo que queda.

Esa reducción a la mitad es la razón de su eficiencia. Partiendo de n candidatos, después de k pasos quedan n/2ᵏ; el proceso acaba cuando n/2ᵏ < 1, es decir cuando k > log₂ n. El peor caso son ⌊log₂ n⌋ + 1 comparaciones: 20 para un millón de elementos, 30 para mil millones. La búsqueda lineal necesitaría un millón. El precio es que el arreglo debe estar ordenado, así que la técnica compensa cuando se busca muchas veces sobre datos que cambian poco.

La clave de la corrección es el invariante: si x está en el arreglo, su posición siempre queda dentro de [lo, hi]. Mientras el invariante se mantenga y el intervalo se reduzca en cada iteración, el algoritmo termina y acierta. Dos detalles delicados: calcular el punto medio como lo + (hi − lo)/2 en lugar de (lo + hi)/2 evita desbordamientos, y la comparación del bucle debe ser lo ≤ hi para no perder el último candidato. La misma idea, aplicada a una función continua monótona, es el método de bisección para hallar raíces.

Fórmulas clave

• Punto medio seguromid = lo + ⌊(hi − lo) / 2⌋
• Candidatos restantesn / 2ᵏ tras k comparaciones
• Peor casok = ⌊log₂ n⌋ + 1 comparaciones
• Invariantex ∈ a ⇒ lo ≤ pos(x) ≤ hi
• Comparación de costesn = 10⁶ : lineal 10⁶ frente a binaria 20

Dónde se aplica

Los índices B-tree de una base de datos son búsqueda binaria generalizada a disco: cada nodo descarta una gran parte del espacio de claves, y por eso una consulta por clave primaria sobre millones de filas es instantánea. Los sistemas de control de versiones ofrecen git bisect, que localiza el commit que introdujo un error probando O(log n) versiones en lugar de todas. En cálculo numérico, la bisección encuentra raíces de ecuaciones no lineales con la misma lógica, y en videojuegos y gráficos se usa para buscar el fotograma o el nivel de detalle adecuado dentro de tablas precalculadas.

Con programación (Python)

import math

def binaria(a, x, verboso=False):
    lo, hi, pasos = 0, len(a) - 1, 0
    while lo <= hi:
        pasos += 1
        mid = lo + (hi - lo) // 2
        if verboso:
            print(f"  paso {pasos}: lo={lo} hi={hi} mid={mid} a[mid]={a[mid]}")
        if a[mid] == x:
            return mid, pasos
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, pasos

a = [2 * i + 1 for i in range(64)]        # impares 1, 3, 5, ..., 127
print("Buscamos 81 en 64 impares ordenados:")
pos, pasos = binaria(a, 81, True)
print("posicion:", pos, " pasos:", pasos, " cota:", int(math.log2(64)) + 1)

peor = max(binaria(a, v)[1] for v in a)
medio = sum(binaria(a, v)[1] for v in a) / len(a)
print("binaria  -> peor:", peor, " promedio:", round(medio, 3))
print("lineal   -> peor:", len(a), " promedio:", (len(a) + 1) / 2)

La versión en JavaScript, editable y ejecutable en el navegador, está en la página interactiva del tema.

Temas relacionados

Complejidad y notación O grande · Algoritmos de ordenamiento · Método de bisección