Búsqueda binaria: cómo encontrar algo entre millones en 20 pasos

Imagina que tengo un directorio telefónico de mil millones de nombres ordenados alfabéticamente y te pido que busques a "Marta Ríos". No vas a empezar por la letra A. Abres el libro por la mitad, miras en qué letra estás, y decides si tu nombre está antes o después. Cortas en dos. Luego vuelves a abrir esa mitad por la mitad. Y otra vez. En unas 30 aperturas, has encontrado a Marta entre mil millones.

Eso es búsqueda binaria: el algoritmo que convierte O(n) en O(log n) aprovechando una sola cosa, que los datos estén ordenados. Es, junto con hashing, el algoritmo más impactante en la práctica. Aparece en bases de datos, compiladores, motores de búsqueda y en la función sort de tu lenguaje favorito.

Este es el segundo artículo de Cómo se busca y se recorre.

La idea central: divide y vencerás

La búsqueda binaria es el ejemplo canónico del paradigma "divide y vencerás":

1. Miramos el elemento central del array.

2. Si es el objetivo, listo.

3. Si es mayor que el objetivo, buscamos solo en la mitad izquierda.

4. Si es menor, buscamos en la mitad derecha.

5. Repetimos hasta encontrarlo o agotar el espacio.

Cada iteración descarta la mitad del espacio de búsqueda. De ahí la complejidad:

1,000,000,000 → 500,000,000 → 250,000,000 → ... → 1
      (≈30 pasos, porque log₂(10⁹) ≈ 30)

Cómo se vería en memoria

Array ordenado: [1, 3, 5, 7, 9, 11, 13, 15, 17], buscamos 11.

paso 1: low=0, high=8, mid=4, arr[4]=9  →  9 < 11, buscar derecha
paso 2: low=5, high=8, mid=6, arr[6]=13 → 13 > 11, buscar izquierda
paso 3: low=5, high=5, mid=5, arr[5]=11 → encontrado en índice 5

Tres comparaciones para 9 elementos; sin búsqueda binaria hubiéramos hecho hasta 9.

Implementación iterativa en PHP

function busquedaBinaria(array $arr, int $objetivo): int {
    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        $mid = intdiv($low + $high, 2);
        if ($arr[$mid] === $objetivo) {
            return $mid;
        } elseif ($arr[$mid] < $objetivo) {
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
    }
    return -1;
}

echo busquedaBinaria([1, 3, 5, 7, 9, 11, 13, 15, 17], 11); // 5

PHP no trae búsqueda binaria en su stdlib, pero escribirla es trivial.

Implementación iterativa en Java

public static int busquedaBinaria(int[] arr, int objetivo) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == objetivo) return mid;
        if (arr[mid] < objetivo) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

Java ya trae Arrays.binarySearch y Collections.binarySearch para primitivos y colecciones:

int i = Arrays.binarySearch(arr, 11);

El contrato: si lo encuentra, devuelve el índice; si no, devuelve -(insertionPoint) - 1. Ese formato extraño permite insertar el elemento manteniendo orden.

Implementación recursiva

Algunos la prefieren recursiva porque sigue de cerca la definición "divide y vencerás":

public static int busquedaBinaria(int[] arr, int objetivo, int low, int high) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (arr[mid] == objetivo) return mid;
    if (arr[mid] < objetivo) return busquedaBinaria(arr, objetivo, mid + 1, high);
    return busquedaBinaria(arr, objetivo, low, mid - 1);
}

Ocupa O(log n) espacio en la pila. En arrays grandes, la versión iterativa es preferible en lenguajes sin TCO (PHP, Java).

El bug clásico: overflow en el cálculo de mid

Por años, Arrays.binarySearch en Java tuvo un bug sutil. La fórmula ingenua:

int mid = (low + high) / 2;

Si low y high son cercanos a Integer.MAX_VALUE, low + high desborda y se convierte en un número negativo. Luego dividido entre 2 da un índice incorrecto.

La fórmula correcta:

int mid = low + (high - low) / 2;

Matemáticamente equivalente pero nunca desborda. Es un patrón que conviene usar siempre, aunque tus arrays sean pequeños. Este bug estuvo dormido en la stdlib de Java ~9 años.

Prerrequisito crucial: la colección debe estar ordenada

Búsqueda binaria solo funciona sobre datos ordenados. Si no lo están, debes ordenarlos primero. Ordenar es O(n log n), así que si vas a buscar una sola vez, sale más caro que una búsqueda lineal O(n). Búsqueda binaria vale la pena cuando:

• Los datos ya están ordenados (lo que es común en índices, archivos, DBs).

• Vas a buscar muchas veces sobre el mismo array.

Variantes útiles

La búsqueda binaria "clásica" devuelve si el elemento existe, pero en la práctica hay variantes con muchísimo valor.

1. Lower bound

Encuentra el primer índice donde aparece el objetivo, o el punto de inserción si no existe. Útil para duplicados:

static int lowerBound(int[] arr, int objetivo) {
    int low = 0, high = arr.length;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] < objetivo) low = mid + 1;
        else high = mid;
    }
    return low;
}

2. Upper bound

El primer índice con valor estrictamente mayor al objetivo. Lower + upper juntos te dan el rango de elementos iguales:

static int upperBound(int[] arr, int objetivo) {
    int low = 0, high = arr.length;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] <= objetivo) low = mid + 1;
        else high = mid;
    }
    return low;
}

Ejemplo: en [1, 2, 2, 2, 3] buscando 2, lowerBound = 1, upperBound = 4, hay 3 ocurrencias.

3. Búsqueda en un array rotado

Casos de entrevista: dado un array ordenado que fue rotado (ej. [4,5,6,7,0,1,2]), encontrar un elemento en O(log n). Se logra identificando qué mitad sigue ordenada y decidiendo dónde está el objetivo.

4. Búsqueda binaria sobre una función monótona

La versión más poderosa: la "respuesta" es un valor entre lo y hi, y sabes que una función f(x) es monótona (creciente o decreciente). Buscas binariamente el x donde f(x) cumple una condición.

Ejemplos:

• El menor número de barcos para transportar toda la carga antes de un deadline.

• La menor velocidad de lectura para terminar todos los libros en H horas.

• La longitud mínima de segmento que cumple cierta propiedad.

Estos problemas aparecen constantemente en programación competitiva y en sistemas reales (rate limiting, capacity planning).

Complejidad

EscenarioTiempoEspacioIterativaO(log n)O(1)RecursivaO(log n)O(log n) por la pila

El logaritmo es base 2: log₂(10⁹) ≈ 30, log₂(10¹²) ≈ 40. Incluso con trillones de elementos, búsqueda binaria hace menos de 50 comparaciones.

Búsqueda binaria en bases de datos

Los índices B-tree de MySQL, PostgreSQL y SQLite son una generalización de búsqueda binaria a árboles de mucho fanout (cada nodo tiene cientos de hijos en vez de 2). El principio es el mismo: descartar una gran porción del espacio en cada paso. Por eso las queries con WHERE columna_indexada = X son tan rápidas aunque la tabla tenga millones de filas.

Cuando haces un CREATE INDEX, la base de datos está construyendo una estructura que permite búsqueda binaria (o similar) sobre esa columna. Cuando añades un WHERE columna = X sobre una columna sin índice, estás forzando búsqueda lineal O(n) (fulltable scan).

Ventajas y desventajas

Ventajas:

• O(log n): extraordinariamente rápida para datos grandes.

• Implementación sencilla (si manejas bien los bordes).

• Útil más allá de arrays: funciones monótonas, problemas de búsqueda de parámetros.

Desventajas:

• Requiere datos ordenados.

• No funciona sobre listas enlazadas (porque no hay acceso aleatorio O(1)).

• Muy sensible a errores off-by-one (mid +1/-1).

Casos de uso reales

1. Índices de bases de datos: B-trees.

2. Arrays.binarySearch y Collections.binarySearch en Java.

3. Búsqueda en estructuras como TreeMap/TreeSet (variante sobre BST).

4. Compiladores: búsqueda de símbolos en una tabla ordenada.

5. Optimización: encontrar el mejor parámetro que cumple una propiedad monótona.

6. Problemas tipo "smallest/largest que cumple X": muchísimos.

7. Implementación de conjuntos ordenados.

8. Algoritmos sobre intervalos y rangos (scheduling, detección de solapamientos).

Ejemplo aplicado: "¿capacidad mínima del barco?"

Problema clásico: tenemos pesos [1, 2, 3, 4, 5, 10] y D = 3 días para transportarlos, en orden. ¿Cuál es la capacidad mínima del barco para lograrlo?

La capacidad mínima posible es max(pesos) = 10 (si no, algún peso no cabe). La máxima útil es sum(pesos) = 25 (todo en un viaje). Entre 10 y 25, la función "¿se puede con capacidad c?" es monótona: si se puede con 15, también con 16. Búsqueda binaria:

static int capacidadMinima(int[] pesos, int D) {
    int low = Arrays.stream(pesos).max().getAsInt();
    int high = Arrays.stream(pesos).sum();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (sePuede(pesos, D, mid)) high = mid;
        else low = mid + 1;
    }
    return low;
}

static boolean sePuede(int[] pesos, int D, int cap) {
    int dias = 1, carga = 0;
    for (int p : pesos) {
        if (carga + p > cap) { dias++; carga = 0; }
        carga += p;
    }
    return dias <= D;
}

Este patrón se repite muchísimo: búsqueda binaria sobre el parámetro, con una función check monótona. Aprenderlo es un superpoder.

Errores comunes

1. Off-by-one en los límites

¿high = n o high = n - 1? ¿low < high o low <= high? ¿mid + 1 o mid? Esos pequeños cambios definen si implementas búsqueda exacta, lower bound o upper bound. Sé consistente con una de las plantillas y apégate a ella.

2. Overflow en low + high

Como mencioné: usa low + (high - low) / 2.

3. Olvidar que el array debe estar ordenado

Si el array está desordenado, búsqueda binaria devuelve basura (a veces encuentra, a veces no). Ordena primero o cambia de algoritmo.

4. Usarla sobre listas enlazadas

Acceso a lista.get(mid) en una LinkedList es O(n), lo que convierte tu "binaria" en O(n log n). Búsqueda binaria solo tiene sentido con acceso aleatorio O(1).

5. Bucles infinitos

Si no actualizas bien low o high, el bucle no progresa. Clásico: olvidar mid + 1 o mid - 1 y caer en el mismo mid para siempre.

6. Asumir que binarySearch devuelve -1 si no encuentra

En Java, Arrays.binarySearch devuelve -(insertionPoint) - 1. No es -1. Manejar eso correctamente requiere leer el Javadoc con cuidado.

7. Usar sobre floats sin tolerancia

En búsqueda binaria sobre dominios continuos (floats), comparar con == casi siempre falla por precisión. Define un epsilon y detente cuando high - low < epsilon.

Resumen

La búsqueda binaria divide el espacio en mitades sucesivas para encontrar un elemento en O(log n), siempre y cuando los datos estén ordenados. Sus variantes (lower bound, upper bound, búsqueda sobre función monótona, búsqueda en arrays rotados) resuelven problemas más complejos.

Es el cimiento de los índices de bases de datos, de Arrays.binarySearch, de las estructuras TreeMap/TreeSet, y de innumerables problemas algorítmicos. Maneja con cuidado los bordes y el cálculo de mid para evitar overflow.

En el siguiente artículo cambiamos de foco: ya no buscar, sino recorrer. Vemos los tres recorridos clásicos de un árbol binario (inorden, preorden, postorden) y qué produce cada uno.