Búsqueda binaria: algoritmo, complejidad O(log n), variantes y errores típicos

¿Cómo encuentras una palabra en un diccionario de papel? No lo lees página por página: lo abres por la mitad, ves si la palabra va antes o después y repites con esa mitad. Esa es la búsqueda binaria, y con ella se encuentra un elemento entre mil millones en solo 30 pasos. Solo exige una cosa: que los datos estén ordenados.

Lo que vas a aprender

La diferencia entre búsqueda lineal y binaria.
El algoritmo paso a paso, en versión iterativa y recursiva.
Por qué su coste es $O(\log n)$ .
Las variantes para encontrar la primera o la última aparición.
La búsqueda binaria sobre la respuesta.
Los errores típicos al programarla.

Fundamentos teóricos

Búsqueda lineal

Recorrer los elementos uno a uno hasta encontrar el buscado. Funciona con cualquier lista, ordenada o no, pero en el peor caso mira todos:

O(n)

Búsqueda binaria

Con la lista ordenada:

Mira el elemento del medio.
Si es el buscado, termina.
Si el buscado es menor, sigue solo con la mitad izquierda; si es mayor, con la derecha.
Repite hasta encontrarlo o hasta que el intervalo quede vacío.

def busqueda_binaria(a, x):
    izq, der = 0, len(a) - 1
    while izq <= der:
        medio = (izq + der) // 2
        if a[medio] == x:
            return medio
        elif a[medio] < x:
            izq = medio + 1
        else:
            der = medio - 1
    return -1          # no está

Versión recursiva:

def bb_rec(a, x, izq, der):
    if izq > der:
        return -1
    medio = (izq + der) // 2
    if a[medio] == x:
        return medio
    if a[medio] < x:
        return bb_rec(a, x, medio + 1, der)
    return bb_rec(a, x, izq, medio - 1)

Es un ejemplo de divide y vencerás en el que solo se sigue por una de las dos mitades.

Por qué es O(log n)

Cada paso divide por 2 el tamaño del intervalo. Tras

k

pasos quedan

n/2^k

elementos; se acaba cuando queda 1, es decir, tras

k = \log_2 n

pasos. La recurrencia es

T(n) = T(n/2) + O(1)

(ver notación asintótica).

$n$	Lineal (peor caso)	Binaria (peor caso)
1000	1000	10
1 000 000	1 000 000	20
1 000 000 000	1 000 000 000	30

Variantes

Con elementos repetidos, a menudo interesa la primera posición donde a[i] >= x (lower bound) o la primera donde a[i] > x (upper bound). Con ellas se cuenta cuántas veces aparece un valor: upper - lower.

def lower_bound(a, x):
    izq, der = 0, len(a)          # intervalo semiabierto [izq, der)
    while izq < der:
        medio = (izq + der) // 2
        if a[medio] < x:
            izq = medio + 1
        else:
            der = medio
    return izq

En Python ya existe: bisect.bisect_left y bisect.bisect_right. En C++, std::lower_bound; en Java, Arrays.binarySearch y Collections.binarySearch.

Búsqueda binaria sobre la respuesta

No hace falta un array: sirve para cualquier función monótona. Si se busca el menor valor que cumple una condición y “cumplir” es monótono (a partir de cierto punto siempre se cumple), se puede buscar ese punto por bisección. Es la misma idea que el método de bisección para resolver ecuaciones.

Ejemplos resueltos

Ejemplo 1 · Traza de una búsqueda

Buscar 23 en [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]:

Paso	izq	der	medio	a[medio]	Decisión
1	0	9	4	16	23 > 16: derecha
2	5	9	7	56	23 < 56: izquierda
3	5	6	5	23	Encontrado en la posición 5

Ejemplo 2 · Contar apariciones

En [1, 2, 2, 2, 3, 5], lower_bound(a, 2) = 1 y bisect_right(a, 2) = 4: el 2 aparece

4 - 1 = 3

veces, en

O(\log n)

Ejemplo 3 · Raíz cuadrada entera

El mayor entero

r

con

r^2 \le n

def raiz_entera(n):
    izq, der = 0, n
    while izq < der:
        medio = (izq + der + 1) // 2
        if medio * medio <= n:
            izq = medio
        else:
            der = medio - 1
    return izq

print(raiz_entera(1_000_000))   # 1000
print(raiz_entera(99))          # 9

Ejemplo 4 · Búsqueda sobre la respuesta

Hay que repartir libros de 100, 200, 300 y 400 páginas, en orden, entre 2 personas, minimizando el máximo que lee una. Se prueba con un máximo

M

: ¿se puede repartir sin superarlo? Si se puede con

M

, también con

M + 1

(monótono). Bisección entre 400 y 1000: la respuesta es 600 (100 + 200 + 300 y 400).

Errores frecuentes

Aplicarla a datos sin ordenar. El resultado no tiene sentido.
Bucles infinitos por actualizar mal los límites (izq = medio en lugar de medio + 1 con un intervalo cerrado).
Confundir intervalo cerrado [izq, der] y semiabierto [izq, der): cambian la condición del bucle y las actualizaciones.
Desbordamiento del punto medio en lenguajes con enteros de tamaño fijo: (izq + der) / 2 puede desbordar con valores enormes. Se usa izq + (der - izq) / 2. Este fallo estuvo años en la biblioteca estándar de Java hasta 2006.
Ordenar para hacer una sola búsqueda. Ordenar cuesta $O(n\log n)$ ; para buscar una vez es mejor la lineal.

Preguntas frecuentes

¿Cuándo compensa ordenar para usar búsqueda binaria?

Cuando se van a hacer muchas búsquedas: ordenar una vez cuesta

O(n\log n)

y cada búsqueda

O(\log n)

. Si además hay que insertar y borrar, mejor un árbol equilibrado; si solo se busca por igualdad, una tabla hash, con

O(1)

de media.

¿Dónde se usa la búsqueda binaria?

En los índices de las bases de datos (árboles B, una generalización), en git bisect para encontrar el commit que introdujo un error (ver Git), en la depuración de cualquier cosa (“¿falla con la mitad de los datos?”) y en muchos problemas de optimización.

Temas relacionados

Algoritmos de ordenación

Ordenar antes de buscar.

Notación asintótica

O(log n) frente a O(n).

Ceros de funciones

El método de bisección.

Matemáticas

Física

Química

Electrónica

Programación

Inglés

Infantil

Búsqueda binaria: algoritmo, complejidad O(log n), variantes y errores típicos

Lo que vas a aprender

Fundamentos teóricos

Búsqueda lineal

Búsqueda binaria

Por qué es O(log n)

Variantes

Búsqueda binaria sobre la respuesta

Ejemplos resueltos

Errores frecuentes

Preguntas frecuentes

Temas relacionados

Algoritmos de ordenación

Notación asintótica

Ceros de funciones

​Lo que vas a aprender

​Fundamentos teóricos

​Búsqueda lineal

​Búsqueda binaria

​Por qué es O(log n)

​Variantes

​Búsqueda binaria sobre la respuesta

​Ejemplos resueltos

​Errores frecuentes

​Preguntas frecuentes

​Temas relacionados

Algoritmos de ordenación

Notación asintótica

Ceros de funciones

Lo que vas a aprender

Fundamentos teóricos

Búsqueda lineal

Búsqueda binaria

Por qué es O(log n)

Variantes

Búsqueda binaria sobre la respuesta

Ejemplos resueltos

Errores frecuentes

Preguntas frecuentes

Temas relacionados