> ## Documentation Index
> Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt
> Use this file to discover all available pages before exploring further.

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

> La búsqueda binaria explicada: búsqueda lineal frente a binaria, el algoritmo paso a paso, versiones iterativa y recursiva, por qué es O(log n), variantes (primera y última aparición, punto de inserción), búsqueda binaria sobre la respuesta y errores típicos como el desbordamiento del punto medio, con código y ejemplos.

¿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**:

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

```python theme={null}
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:

```python theme={null}
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](https://apuntes.simulab.es/programacion/c/divide-y-venceras.md) 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](https://apuntes.simulab.es/programacion/algoritmos/notacion-asintotica.md)).

| $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`.

```python theme={null}
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](https://apuntes.simulab.es/matematicas/metodos-numericos/ceros-funciones.md) para resolver ecuaciones.

## Ejemplos resueltos

> [accordion] 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 |

> [accordion] 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)$.

> [accordion] Ejemplo 3 · Raíz cuadrada entera
>
> El mayor entero $r$ con $r^2 \le n$:
>
> ```python theme={null}
> 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
> ```

> [accordion] 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

> [accordion] ¿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](https://apuntes.simulab.es/programacion/algoritmos/arboles-avl.md); si solo se busca por igualdad, una [tabla hash](https://apuntes.simulab.es/programacion/java/tablas-hash.md), con $O(1)$ de media.

> [accordion] ¿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](https://apuntes.simulab.es/programacion/herramientas/git.md)), en la depuración de cualquier cosa ("¿falla con la mitad de los datos?") y en muchos problemas de optimización.

## Temas relacionados

> [card] [Algoritmos de ordenación](https://apuntes.simulab.es/programacion/algoritmos/ordenacion.md)
>
> Ordenar antes de buscar.

> [card] [Notación asintótica](https://apuntes.simulab.es/programacion/algoritmos/notacion-asintotica.md)
>
> O(log n) frente a O(n).

> [card] [Ceros de funciones](https://apuntes.simulab.es/matematicas/metodos-numericos/ceros-funciones.md)
>
> El método de bisección.


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.