Variantes y trampas

La búsqueda binaria estándar busca un valor exacto en un arreglo ordenado. Las variantes que aparecen en entrevistas exploran qué hacer cuando no encuentras el valor exacto, cuando los datos están "casi ordenados" o cuando aplicas la idea a un espacio distinto.

Variante 1: primera y última aparición

Si el valor aparece varias veces, ¿cuál índice devuelves? La búsqueda binaria estándar te da uno arbitrario.

Para encontrar la primera aparición:

def primera(arr, objetivo):
    izq, der = 0, len(arr) - 1
    resultado = -1
    while izq <= der:
        medio = (izq + der) // 2
        if arr[medio] == objetivo:
            resultado = medio
            der = medio - 1  # seguir buscando a la izquierda
        elif arr[medio] < objetivo:
            izq = medio + 1
        else:
            der = medio - 1
    return resultado

Lo importante: cuando encuentras el valor, no devuelves inmediatamente. Guardás el índice y sigues buscando a la izquierda. Análogamente para última aparición.

Variante 2: encontrar el primer elemento que cumple X

A veces el problema no es "encontrar el valor V", sino "encontrar el primer elemento que cumple cierta condición". Si la condición es monótona (verdadera para todos los elementos a partir de cierto índice y falsa antes), puedes binarizar.

def primer_que_cumple(arr, condicion):
    izq, der = 0, len(arr) - 1
    resultado = -1
    while izq <= der:
        medio = (izq + der) // 2
        if condicion(arr[medio]):
            resultado = medio
            der = medio - 1
        else:
            izq = medio + 1
    return resultado

Ejemplo: encontrar el primer índice donde arr[i] > 100. La función condicion es arr[i] > 100.

Variante 3: búsqueda binaria en arreglo rotado

[4, 5, 6, 7, 0, 1, 2]: el arreglo estaba ordenado pero fue rotado. ¿Cómo encontrar un valor en O(log n)?

Idea: en cada iteración, una de las dos mitades sigue ordenada. Si el objetivo cae en esa mitad ordenada, descartas la otra.

def buscar_rotado(arr, objetivo):
    izq, der = 0, len(arr) - 1
    while izq <= der:
        medio = (izq + der) // 2
        if arr[medio] == objetivo:
            return medio
        # ¿la mitad izquierda está ordenada?
        if arr[izq] <= arr[medio]:
            if arr[izq] <= objetivo < arr[medio]:
                der = medio - 1
            else:
                izq = medio + 1
        else:
            # mitad derecha ordenada
            if arr[medio] < objetivo <= arr[der]:
                izq = medio + 1
            else:
                der = medio - 1
    return -1

Variante 4: búsqueda binaria sobre la respuesta

Algunos problemas no tienen un arreglo ordenado, pero el espacio de respuestas posibles está naturalmente ordenado. Si puedes contestar "¿esta respuesta cumple X?" en tiempo razonable, puedes binarizar sobre el rango de respuestas.

Ejemplo: mínima capacidad para repartir paquetes en N días. Tenés pesos de paquetes y N días para repartirlos en orden. ¿Cuál es la capacidad mínima del camión?

• Mínima posible: el peso del paquete más grande.
• Máxima posible: la suma de todos los pesos (los llevás todos en un día).
• Para cada candidato C, cuentas cuántos días necesitas. Si necesitas ≤ N días, C es válido.

def capacidad_minima(pesos, dias):
    def es_valido(capacidad):
        d, carga = 1, 0
        for p in pesos:
            if carga + p > capacidad:
                d += 1
                carga = 0
            carga += p
        return d <= dias
    
    izq, der = max(pesos), sum(pesos)
    while izq < der:
        medio = (izq + der) // 2
        if es_valido(medio):
            der = medio
        else:
            izq = medio + 1
    return izq

Nota que NO buscamos un valor en un arreglo. Buscamos en el rango [max(pesos), sum(pesos)]. Esa es la respuesta.

Los bugs más comunes

Loop infinito por mover índices mal

# MAL: puede entrar en loop
while izq <= der:
    medio = (izq + der) // 2
    if arr[medio] < objetivo:
        izq = medio  # debería ser medio + 1

Cuando izq == der y arr[medio] < objetivo, izq queda igual. Loop infinito.

Regla: cuando descartas una mitad, asegúrate que el índice avance al menos en 1.

Overflow en el cálculo del medio

# Problema en lenguajes con enteros fijos (C, Java):
medio = (izq + der) // 2  # puede overflow si ambos son grandes

En Python no es problema (enteros arbitrariamente grandes). En C/Java/JS hay que escribir:

int medio = izq + (der - izq) / 2;  // no overflow

En JS los numbers son float64 y pueden representar enteros hasta 2^53. Para arreglos típicos no es problema, pero conviene saber.

Condición de salida < vs <=

while izq <= der:  # incluye el caso izq == der
    ...

while izq < der:  # no incluye
    ...

Cuál usar depende de cómo movés los índices y qué representan. Es la fuente número uno de bugs en BS. Si dudás, simulá con un arreglo de 1 y de 2 elementos: si funciona, casi seguro funciona para todos.

El "boundary" off-by-one

Cuando buscas primera/última aparición o el primer que cumple X, después del loop el índice resultado es válido (-1 si no se encontró) o el ajuste de límites.

Si tu loop termina con izq < der, después del loop izq == der. Verifica manualmente si arr[izq] cumple lo que quieres antes de devolverlo.

La plantilla universal

Para no perderse entre variantes, hay una plantilla que cubre casi todo. La idea: pensar en términos de "predicado monótono" y "primer índice que lo cumple".

def busqueda_binaria(lo, hi, condicion):
    """
    Encuentra el primer índice en [lo, hi] donde condicion(i) = True.
    Si condicion es falsa para todos, devuelve hi + 1.
    """
    while lo < hi:
        medio = (lo + hi) // 2
        if condicion(medio):
            hi = medio
        else:
            lo = medio + 1
    return lo

Adaptás la condición al problema. Para "buscar valor V exacto", la condición es arr[i] >= V. Después verificas si arr[resultado] == V.