Búsqueda binaria: búsqueda rápida en datos ordenados

Al finalizar este tema

Comprenderá el principio de la búsqueda binaria, experimentará por qué O(log n) es eficiente y conocerá los puntos clave a tener en cuenta al implementarla.

Buscar una palabra en un diccionario

Supongamos que busca "Python" en un diccionario impreso. No revisará cada página desde el principio. En su lugar, abrirá el diccionario por la mitad. Si ve que la palabra en el centro está antes de "Python" (por ejemplo, "M"), sabrá que "Python" está en la segunda mitad. Si la palabra está después de "Python" (por ejemplo, "S"), sabrá que está en la primera mitad. Repetirá este proceso, dividiendo el rango de búsqueda a la mitad cada vez.

Este es el principio de la búsqueda binaria. En cada paso, el rango de búsqueda se reduce a la mitad.

Búsqueda secuencial vs. búsqueda binaria

Supongamos que busca el número 73 en una lista ordenada del 1 al 100.

Búsqueda secuencial: 1, 2, 3, ..., 73. Requiere 73 comparaciones.

Búsqueda binaria:

[1 ............... 50 ............... 100]  → 50 < 73 → derecha
[51 ......... 75 ......... 100]             → 75 > 73 → izquierda
[51 .... 63 .... 74]                        → 63 < 73 → derecha
[64 .. 69 .. 74]                            → 69 < 73 → derecha
[70 . 72 . 74]                              → 72 < 73 → derecha
[73]                                        → encontrado!

Lo encontré en el sexto intento. En un conjunto de 100 elementos, la diferencia entre el intento número 6 y el elemento en el índice 73 ya es de 12 veces.

La eficiencia de O(log n)

Con solo 30 comparaciones, se puede encontrar la respuesta en un conjunto de mil millones de datos. Esto es posible porque en cada paso se divide el conjunto a la mitad, y $2^{30} \approx 10^9$.

Implementación

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid          # encontrado
        elif arr[mid] < target:
            left = mid + 1      # mitad derecha
        else:
            right = mid - 1     # mitad izquierda

    return -1                   # no encontrado

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(numbers, 23))  # 5 (índice)
print(binary_search(numbers, 10))  # -1 (no encontrado)

Tres puntos clave

1. El ordenamiento es un requisito previo

La búsqueda binaria solo funciona con datos ordenados. Si los datos no están ordenados, comparar con el valor central no permite determinar si se debe buscar en la mitad izquierda o derecha.

El costo del ordenamiento es O(n log n). Si solo se va a realizar una búsqueda, la búsqueda secuencial O(n) es más rápida. La ventaja de la búsqueda binaria radica en realizar múltiples búsquedas después de ordenar los datos.

2. left <= right (igualdad)

Si se utiliza < en lugar de <= en while left <= right, se omitirá la verificación cuando quede un solo elemento. Esto provoca que no se encuentre el valor correcto si este es el último elemento restante.

3. Desbordamiento en el cálculo de mid

# Cálculo seguro
mid = left + (right - left) // 2

(left + right) // 2 no presenta problemas en Python, pero en lenguajes como C o Java, donde el tamaño de los enteros es fijo, left + right puede producir un desbordamiento. Es más seguro usar este enfoque de forma habitual.

Funciones integradas de Python — bisect

import bisect

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

# Encontrar la posición de inserción
idx = bisect.bisect_left(numbers, 23)
print(idx)  # 5

# Verificar si el valor existe
if idx < len(numbers) and numbers[idx] == 23:
    print("Encontrado")

bisect es un módulo que implementa la búsqueda binaria en C. Es más rápido que una implementación manual y también se puede utilizar para encontrar la posición en la que se debe insertar un valor en una lista ordenada.

Conceptos clave

La búsqueda binaria es un algoritmo que elimina la mitad de los datos en cada paso dentro de un conjunto ordenado. Complejidad temporal O(log n): con 1000 millones de elementos, se encuentra el valor en 30 pasos. El requisito previo es que los datos estén ordenados, lo que resulta especialmente eficaz cuando se realiza una única ordenación seguida de múltiples búsquedas.