Búsqueda binaria

Qué cubre este capítulo

La búsqueda binaria es la recompensa por todo ese trabajo de ordenamiento. Una vez que un array está ordenado, nunca más tienes que recorrerlo completo: para encontrar cualquier cosa, ve al centro y descarta la mitad que no puede contenerla. Repite, y cada paso reduce a la mitad lo que queda, así que mil millones de elementos toman unas treinta comparaciones en vez de mil millones. En este capítulo construimos la búsqueda clásica y las dos variantes que en la práctica importan más — lower_bound y upper_bound, que encuentran dónde iría un valor — y encaramos el secreto sucio de la búsqueda binaria: es uno de los algoritmos más propensos a bugs de toda la computación, y acertarle a los límites exactos es toda la habilidad.

Un poco de historia

La idea de la búsqueda binaria es vieja — así buscas una palabra en el diccionario o un nombre en el directorio telefónico — pero el algoritmo correcto resultó sorprendentemente difícil de fijar. John Mauchly la describió en 1946, y aun así la primera búsqueda binaria publicada sin bugs no apareció hasta 1962; las versiones intermedias traían errores de uno-por-uno y fallas en los límites. Jon Bentley, en su "Programming Pearls" de los ochenta, reportó que cuando le pidió a programadores profesionales escribir una búsqueda binaria, cerca del 90% entregó código con bugs — incluso dándoles horas y un compilador. Y en 2006 se encontró un overflow de enteros sutil en la búsqueda binaria que llevaba dos décadas embarcada en la librería estándar de Java, en los libros de texto y en el propio código de Bentley. Así que la búsqueda binaria es el algoritmo que humilla a todos: trivial de describir, traicionero de implementar, que es justo la razón por la que vale la pena construirla a mano con cuidado una vez.

La intuición

Tienes un array ordenado y quieres saber si contiene cierto valor objetivo. Mira el elemento de en medio. Si es el objetivo, listo. Si el objetivo es menor, solo puede estar en la mitad izquierda — así que descarta la derecha completa y repite sobre la izquierda. Si es mayor, descarta la izquierda. Cada comparación tira a la basura la mitad de lo que queda, así que el número de comparaciones es la cantidad de veces que puedes partir n a la mitad antes de quedarte sin nada: log₂ n.

La búsqueda simple responde "¿está aquí, y dónde?". Pero la pregunta más útil suele ser "¿dónde iría?" — y eso es lower_bound: la primera posición cuyo elemento no es menor que el objetivo, que es exactamente donde insertarías el objetivo para mantener el array ordenado. Funciona esté o no presente el objetivo, el índice que regresa te dice cuántos elementos son menores (una consulta de rango gratis), y junto con upper_bound acota todas las copias de un valor duplicado. El código real usa estas búsquedas de límites mucho más que la de presente-o-no, y por eso bisect expone esas y no un "find" simple.

Complejidad: cómo escala

La búsqueda binaria es $O(\log n)$ en tiempo y $O(1)$ en espacio — una ventana que se parte a la mitad en cada paso, rastreada con dos enteros. Su única precondición dura es que la entrada esté ordenada; con datos sin ordenar regresa basura, y en silencio. La gráfica corre muchas búsquedas sobre arrays ordenados de tamaño creciente, comparando la búsqueda binaria y bisect contra un recorrido lineal:

El recorrido lineal sube con n — es O(n) por consulta — y se sale de la gráfica pasando los diez mil elementos porque se vuelve insoportable. Las dos búsquedas binarias se mantienen casi planas: crecer el array cien veces solo agrega un puñado de sondeos por búsqueda. Esa brecha entre una línea que crece y una que casi no se mueve es todo el argumento para ordenar tus datos.

En qué es buena y en qué no

La búsqueda binaria es la herramienta correcta siempre que tengas datos ordenados y los consultes más de una vez. El ordenamiento es un costo inicial, O(n log n), pero cada búsqueda posterior es O(log n) en vez de O(n), así que se paga rápido en cualquier carga de trabajo con muchas lecturas — una tabla de consulta, un índice ordenado, una config que consultas seguido. Y lower_bound convierte un array ordenado en una mini base de datos: puntos de inserción, consultas de rango (rank), conteos por intervalo y búsquedas de vecino más cercano salen todas de ahí.

Donde es la herramienta equivocada es con datos sin ordenar o que cambian rápido. Si los datos no están ordenados, pagarías O(n log n) por ordenarlos antes de poder buscar — y si solo vas a buscar una vez, un recorrido O(n) simple sale más barato. Si los datos cambian constantemente, mantener el array ordenado cuesta O(n) por inserción (hay que recorrer elementos), lo que normalmente pierde contra un árbol balanceado o una tabla hash. Y cuando solo necesitas saber si algo pertenece al conjunto, sin orden ni consultas de rango, el O(1) de un hash set le gana al O(log n) de la búsqueda binaria. La búsqueda binaria brilla específicamente con datos ordenados, grandes y consultados seguido.

Los datos, o las entradas

El duelo busca sobre arrays ordenados de números pares (así que como la mitad de los objetivos no existen, el peor caso para la búsqueda). La animación busca el valor 30 en un array ordenado de 21 elementos, registrando la ventana en cada sondeo para que la veas colapsar.

Constrúyelo, una función a la vez

La búsqueda clásica — parte la ventana a la mitad hasta encontrar el objetivo o quedarte sin ventana:

def binary_search(values, target, probe=None):
    """O(log n): keep a window [lo, hi); look at the middle; throw away the half that
    can't contain the target. Returns the index of `target`, or -1. The input MUST be
    sorted — that's the precondition the whole method rests on."""
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if probe is not None:
            probe.append({"lo": lo, "hi": hi, "mid": mid})
        if values[mid] == target:
            return mid
        if values[mid] < target:
            lo = mid + 1          # target is in the right half
        else:
            hi = mid              # target is in the left half
    return -1

Lower bound — el primer índice cuyo elemento es al menos el objetivo, es decir, el punto de inserción. Fíjate que no tiene retorno anticipado: siempre se reduce hasta una sola posición, que es lo que hace que funcione esté o no presente el objetivo:

def lower_bound(values, target, probe=None):
    """O(log n): the index of the FIRST element >= target — where target would be
    inserted to keep the array sorted (this is bisect_left). More useful than plain
    search: it works whether or not target is present, and the returned index equals
    the number of elements strictly less than target — a range query for free."""
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if probe is not None:
            probe.append({"lo": lo, "hi": hi, "mid": mid})
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

Upper bound — el primer índice estrictamente mayor que el objetivo; junto con lower_bound acota todas las copias:

def upper_bound(values, target):
    """O(log n): the index of the first element > target (bisect_right). Together with
    lower_bound it brackets every copy of target: the equal elements are exactly the
    slice values[lower_bound : upper_bound]."""
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if values[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

Míralo funcionar

Aquí está la búsqueda binaria cazando el 30 en un array ordenado de 21 elementos. El azul es la ventana viva — donde el objetivo todavía podría estar; el naranja es el elemento de en medio que se está revisando; las celdas oscuras ya se descartaron. Avanza paso a paso y observa cómo la ventana azul se parte a la mitad en cada sondeo: la búsqueda mira el centro, compara y tira medio array, así que una búsqueda de 21 elementos termina en apenas 5 sondeos. Imagina el array mil veces más grande y la ventana igual colapsaría en unos diez pasos más — ese es el logaritmo en acción:

El código completo

Las dos versiones en un solo lugar — cambia entre ellas. La pestaña desde cero tiene la búsqueda y ambos límites. La pestaña de librería es bisect: bisect_left es nuestro lower_bound y bisect_right es nuestro upper_bound, ambos en C. Nota que bisect no tiene un "find" simple — lo armas a partir de bisect_left, porque las búsquedas de límites son la primitiva.

"""Binary search — find an element in a sorted array in O(log n) by repeatedly
halving the search window. It's the payoff for all that sorting: once data is sorted,
you never scan it again.

Beyond the textbook "is it present?" search, the two variants that matter in practice
are lower_bound and upper_bound — they find where a value WOULD go, which works whether
or not it's present and answers range queries. They're the operations behind Python's
`bisect` module, and getting their boundaries exactly right is famously fiddly, which
is why it's worth building them once by hand.
"""


# region: binary_search
def binary_search(values, target, probe=None):
    """O(log n): keep a window [lo, hi); look at the middle; throw away the half that
    can't contain the target. Returns the index of `target`, or -1. The input MUST be
    sorted — that's the precondition the whole method rests on."""
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if probe is not None:
            probe.append({"lo": lo, "hi": hi, "mid": mid})
        if values[mid] == target:
            return mid
        if values[mid] < target:
            lo = mid + 1          # target is in the right half
        else:
            hi = mid              # target is in the left half
    return -1
# endregion


# region: lower_bound
def lower_bound(values, target, probe=None):
    """O(log n): the index of the FIRST element >= target — where target would be
    inserted to keep the array sorted (this is bisect_left). More useful than plain
    search: it works whether or not target is present, and the returned index equals
    the number of elements strictly less than target — a range query for free."""
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if probe is not None:
            probe.append({"lo": lo, "hi": hi, "mid": mid})
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo
# endregion


# region: upper_bound
def upper_bound(values, target):
    """O(log n): the index of the first element > target (bisect_right). Together with
    lower_bound it brackets every copy of target: the equal elements are exactly the
    slice values[lower_bound : upper_bound]."""
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if values[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo
# endregion

"""Python's `bisect` module is binary search done right — `bisect_left` is our
lower_bound, `bisect_right` is our upper_bound, both in C. It's the standard way to
search a sorted list and to keep a list sorted as you insert (`insort`). There's no
plain "find the index of x" in bisect; you build it from bisect_left, exactly as below.

The face-off is our binary search against `bisect` and against a linear scan — the
O(log n) vs O(n) gap that is the whole reason to keep data sorted.
"""
import bisect


# region: bisect_lib
def search_bisect(values, target):
    """Locate target via bisect_left, then confirm it's actually there."""
    i = bisect.bisect_left(values, target)
    return i if i < len(values) and values[i] == target else -1


def lower_bound_bisect(values, target):
    return bisect.bisect_left(values, target)


def upper_bound_bisect(values, target):
    return bisect.bisect_right(values, target)
# endregion


# region: linear
def linear_search(values, target):
    """The O(n) baseline: scan until found. This is what binary search replaces —
    and the reason the difference is worth a sort."""
    for i, v in enumerate(values):
        if v == target:
            return i
    return -1
# endregion

Desde cero vs librería

Ambas búsquedas binarias son O(log n), así que la diferencia es la constante de siempre. Dos mil búsquedas sobre un array de un millón de elementos le tomaron a nuestra búsqueda binaria unos 2.8 ms y a bisect unos 0.66 ms — bisect como cuatro veces más rápido, por ser C contra Python. Pero ponlo al lado del recorrido lineal, que ni siquiera aparece en la gráfica pasando los diez mil elementos porque O(n) por consulta se vuelve inservible. Esa es la comparación que importa: búsqueda binaria contra bisect es un factor constante; búsqueda binaria contra lineal es un abismo de clase de complejidad, O(log n) contra O(n). La lección correcta no es "usa bisect porque es más rápido que mi código" (aunque sí deberías) — es "busca en datos ordenados con un logaritmo, nunca con un recorrido".

Dónde te la vas a encontrar de verdad

La búsqueda binaria está en todos lados donde hay datos ordenados. bisect.insort mantiene una lista en orden conforme llegan los elementos; las bases de datos buscan binariamente dentro de las páginas ordenadas de un índice B-tree (capítulo posterior); git bisect busca binariamente en tu historial de commits para hallar el que introdujo un bug; los resolvedores de versiones buscan binariamente releases compatibles. Cualquier autocompletado o filtro de rango sobre datos ordenados usa lower/upper bound. Y la "búsqueda binaria sobre la respuesta" optimiza calladamente desde rate limiters hasta scheduling. La búsqueda simple en un array es solo el miembro más visible de una familia que aparece cada vez que un problema tiene una estructura ordenada que explotar.

Puntos clave

La búsqueda binaria encuentra un elemento, o su punto de inserción, en un array ordenado en $O(\log n)$ partiendo la ventana de búsqueda a la mitad en cada paso — la razón por la que un ordenamiento único se paga solo a lo largo de muchas búsquedas. Las variantes de límites, lower_bound y upper_bound, son los caballitos de batalla: localizan dónde va un valor esté o no presente y responden consultas de rango gratis. Su precondición (datos ordenados) y sus famosos bugs de límites son las dos cosas que hay que respetar — que es una excelente razón para echar mano de bisect.

Queda un capítulo en este nivel, y es un giro precioso sobre el ordenamiento. Quickselect encuentra el k-ésimo elemento más pequeño — la mediana, un percentil, el umbral del top-k — en $O(n)$ sin ordenar el array para nada, reutilizando la partición de quicksort y recursando solo en el lado que contiene la respuesta. Es la última idea del arco de recursión y ordenamiento, y lo cierra mostrando que a veces no necesitas todo el orden completo para encontrar lo que buscas.