Búsqueda binaria clásica

Tema: Búsqueda Binaria · temarios: Syllabus OCI · Syllabus IOI

📍 Dónde se aprende: módulo 08 de la Ruta de Aprendizaje.

El problema: buscar sin mirar cada elemento

Tenemos el arreglo ordenado a = [2, 4, 4, 7, 9, 12, 15, 20] y queremos encontrar el 9. Recorrerlo funciona, pero cuesta O(n) por búsqueda. El orden permite descartar muchos candidatos con una sola comparación.

Si miramos el 7, todo lo que queda a su izquierda también es menor que 9. Si miramos el 12, todo lo que queda a su derecha también es mayor que 9. Elegimos la posición central para que cualquiera de los descartes reduzca aproximadamente a la mitad el intervalo pendiente.

Seguir los candidatos

Aquí l y r son índices incluidos en la búsqueda. Las casillas atenuadas ya se descartaron; el borde más grueso señala el elemento que comparamos.

Paso 120414273941251562077 < 9Paso 2204142739412515620712 > 9Paso 320414273941251562079 = 9

Si el diagrama no cabe, deslízalo horizontalmente.

PasoIntervalo de índicesMedio y valorDecisión
1[0, 7]3 → 77 < 9: seguir en [4, 7]
2[4, 7]5 → 1212 > 9: seguir en [4, 4]
3[4, 4]4 → 9Encontrado en el índice 4

Si buscáramos 10, el último paso dejaría l = 5 y r = 4: el intervalo queda vacío y sabemos que el valor no está. No necesitamos revisar lo descartado.

Por qué podemos descartar sin perder la respuesta

La propiedad que conservamos es: si el valor existe y todavía no lo encontramos, alguna aparición está en [l, r]. Cuando a[mitad] < x, ninguna posición hasta mitad puede servir porque el arreglo está ordenado. El argumento simétrico permite descartar desde mitad hacia la derecha.

Los cambios mitad + 1 y mitad - 1 excluyen una posición que ya revisamos. Así el intervalo se reduce incluso cuando tiene uno o dos elementos. Esta convención corresponde al código de abajo; otras variantes usan rangos semiabiertos y reglas distintas que no conviene mezclar.

Tras cada comparación queda como máximo la mitad de los candidatos: el tiempo es O(log n) y la memoria adicional O(1). Ordenar previamente cuesta O(n log n), por lo que para una única búsqueda puede convenir el recorrido lineal.

Implementación y herramientas de la biblioteca

// Versión manual: ¿está x? Devuelve una posición donde está, o -1.
int buscar(const vector<int>& a, int x) {        // a DEBE venir ordenado
    int l = 0, r = (int)a.size() - 1;
    while (l <= r) {
        int mitad = l + (r - l) / 2;             // evita el overflow de (l+r)/2
        if (a[mitad] == x) return mitad;
        if (a[mitad] < x) l = mitad + 1;         // x está a la derecha
        else              r = mitad - 1;         // x está a la izquierda
    }
    return -1;
}
 
// En competencia se usa la STL: mismo O(log n) y sin bugs de ±1.
vector<int> a = {2, 4, 4, 7, 9};
bool esta    = binary_search(a.begin(), a.end(), 7);            // ¿está? -> true
int  menores = lower_bound(a.begin(), a.end(), 4) - a.begin();  // cuántos < 4 -> 1
int  hasta   = upper_bound(a.begin(), a.end(), 4) - a.begin();  // cuántos <= 4 -> 3
int  iguales = hasta - menores;                                 // cuántos == 4 -> 2
 
// cuántos caen en el rango [lo, hi]:
int lo = 4, hi = 9;
int en_rango = upper_bound(a.begin(), a.end(), hi) - lower_bound(a.begin(), a.end(), lo);

La función buscar(a, 9) devuelve 4 en nuestro ejemplo; buscar(a, 10) devuelve −1. Con repetidos devuelve alguna aparición, no necesariamente la primera. El cálculo l + (r - l) / 2 evita sumar directamente los extremos grandes. Esta versión usa índices int: supone que el tamaño del arreglo cabe en ese tipo.

Los ejemplos de biblioteca del bloque usan un arreglo más corto, [2,4,4,7,9]:

NecesidadHerramientaResultado para x = 4
Saber si existebinary_searchtrue
Primera posición con valor ≥ xlower_boundíndice 1
Primera posición con valor > xupper_boundíndice 3
Contar aparicionesrestar esos dos iteradores2

Un límite puede ser a.end(): es la posición posterior al último elemento, no una casilla que puedas leer. lower_bound tampoco certifica que x exista: para buscar 5 en ese arreglo devuelve la posición del 7.

Elegir la variante

Usa esta búsqueda cuando los datos están ordenados. En un set o map, usa su método lower_bound: la función genérica sobre sus iteradores puede realizar O(n) avances, aunque haga O(log n) comparaciones.

Cuando buscas una respuesta numérica y puedes comprobar si es factible, la idea se extiende a Búsqueda binaria sobre la respuesta. Allí debes justificar primero que la condición cambia una sola vez.

al buscar 4?

Comparar el medio, que contiene 9, descarta la mitad derecha, justo donde está el 4. Buscar 9 en ese mismo arreglo sí acertaría, pero un acierto aislado no reemplaza la condición de que el arreglo esté ordenado.

Más ejemplos y práctica en 08 - Búsqueda binaria.