Introducción a la Búsqueda Binaria

Si tienes que buscar un valor en un arreglo de un millón de números ordenados, una búsqueda lineal puede hacer hasta un millón de comparaciones. Una búsqueda binaria hace como mucho 20.

Como los datos están ordenados, cada vez que miras el elemento del medio sabes en cuál de las dos mitades puede estar la respuesta. La otra mitad se descarta entera.

La mecánica

Mantienes dos índices, izquierda y derecha, que delimitan la región donde la respuesta podría estar. En cada paso miras arr[medio], lo comparas con tu objetivo, y mueves uno de los dos índices.

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

Cuatro cosas que tienen que estar en cualquier búsqueda binaria que escribas:

1. Dos índices que delimitan la región donde queda por buscar.
2. Una forma de calcular el medio sin caer en un índice fuera del arreglo.
3. Una condición de salida del loop.
4. Movimientos de los índices que garanticen que la región se reduce en cada paso.

Por qué es O(log n)

En cada iteración descartas la mitad de los elementos que quedaban. Empiezas con n, después n/2, después n/4. La cantidad de pasos hasta llegar a 1 es log₂(n). Para n = 1.000.000 son aproximadamente 20 pasos.

El espacio adicional es O(1) en la versión iterativa. La recursiva gasta O(log n) por la pila de llamadas, así que normalmente se prefiere la iterativa.

El requisito: orden

La búsqueda binaria funciona cuando los datos están ordenados según algún criterio. El criterio no tiene que ser numérico:

• Strings en orden alfabético.
• Timestamps cronológicos.
• Un rango de enteros del 1 al N.
• Un arreglo de objetos con cualquier comparador consistente.

El bug más común: el loop infinito

Pasa cuando los índices se mueven mal y nunca llegan a cruzarse. Las reglas que evitan el problema:

• Si arr[medio] < objetivo, asigna izquierda = medio + 1, no medio.
• Si arr[medio] > objetivo, asigna derecha = medio - 1, no medio.
• Si la condición del loop es < en vez de <=, ajusta el cálculo del medio y los movimientos para no saltarte el último elemento.

Cuando dudes, ejecuta el algoritmo a mano con un arreglo de dos elementos. Si funciona ahí, funciona con un millón.

Lo que practicas en este tema

Los problemas que vienen después cubren tres variantes:

1. Encontrar el valor exacto en un arreglo ordenado.
2. Encontrar la primera aparición de un valor que aparece varias veces.
3. Búsqueda binaria sobre el espacio de respuestas, aplicada a raíz cuadrada entera.