Algoritmo de búsqueda binaria: cómo funciona con ejemplos

La búsqueda binaria localiza un elemento en un array ordenado en O(log n) comparaciones, frente a las O(n) de la búsqueda lineal. Con un millón de elementos, la búsqueda lineal puede necesitar un millón de comparaciones; la binaria necesita como máximo 20.

Cómo funciona paso a paso

El algoritmo divide el array por la mitad en cada iteración:

1. Define dos punteros: izquierda = 0, derecha = n-1.
2. Calcula el elemento central: medio = (izquierda + derecha) // 2.
3. Si el elemento central es el buscado, retorna su índice.
4. Si el buscado es menor, mueve derecha = medio - 1.
5. Si el buscado es mayor, mueve izquierda = medio + 1.
6. Repite hasta encontrarlo o hasta que izquierda > derecha (no existe).

Implementación en Python

def busqueda_binaria(arr, objetivo):
    izquierda, derecha = 0, len(arr) - 1
    while izquierda <= derecha:
        medio = (izquierda + derecha) // 2
        if arr[medio] == objetivo:
            return medio
        elif arr[medio] < objetivo:
            izquierda = medio + 1
        else:
            derecha = medio - 1
    return -1  # no encontrado

Cuándo usarla y cuándo no

La búsqueda binaria requiere que el array esté ordenado. Si el array no está ordenado, hay que ordenarlo primero (O(n log n)), lo que puede hacer que la búsqueda lineal sea más rápida para un solo uso. La binaria es rentable cuando se harán muchas búsquedas sobre los mismos datos ordenados.

También aplica a cualquier búsqueda sobre un espacio de soluciones monótono: encontrar la raíz de una función, calcular la raíz cuadrada entera de un número, buscar el primer elemento que cumple una condición en un array ordenado.

Errores comunes al implementarla

El error más frecuente es el overflow al calcular el punto medio. (izquierda + derecha) / 2 puede desbordarse en lenguajes con enteros de tamaño fijo. La forma segura es izquierda + (derecha - izquierda) / 2. En Python no hay overflow por diseño, pero en C++ o Java sí.

Variantes avanzadas

La búsqueda binaria tiene docenas de variantes según lo que se busca: el primer elemento mayor que X, el último elemento menor que Y, la posición de inserción de un elemento nuevo. La librería estándar de Python incluye bisect.bisect_left y bisect.bisect_right que implementan estas variantes de forma eficiente.

Preguntas frecuentes

¿Funciona la búsqueda binaria en arrays con duplicados? Sí, pero si quieres encontrar la primera o última ocurrencia necesitas ajustar la condición de parada.

¿Cuál es la complejidad espacial de la búsqueda binaria iterativa? O(1), porque solo usa tres variables (izquierda, derecha, medio) independientemente del tamaño del array.