08 · Búsqueda binaria

Buscar soluciones eficientes · Ruta de Aprendizaje

Antes de empezar. Arreglos ordenados de 05 - Ordenamiento y costos de 07 - Cuánto se demora tu programa.

🎯 Objetivos

Al terminar este módulo sabes:

  • Implementar la búsqueda binaria clásica sin bugs de límites.
  • Usar lower_bound y binary_search de la STL.
  • Reconocer cuándo O(n) por consulta es demasiado y O(log n) salva.

📖 La lección

La idea: descartar la mitad

En un arreglo ordenado, comparar x con el elemento del medio descarta media colección de un golpe. Repitiendo, 10⁶ elementos se agotan en ~20 pasos: eso es O(log n) contra el O(n) de la búsqueda lineal del módulo 03. Buscando 23 entre 15 valores:

258121623385672911051201351501701lmra[7] = 56> 23 → izquierda258121623385672911051201351501702lmra[3] = 12< 23 → derecha258121623385672911051201351501703lmra[5] = 23¡está!m = mitad · 15 valores, 3 comparaciones; con un millón, unas 20

Si el diagrama no cabe, deslízalo horizontalmente.

En el dibujo quedan 15 → 7 → 3 candidatos y encontramos el 23 en la tercera comparación. Si todavía no lo encontráramos, el siguiente descarte dejaría uno. Con un millón de elementos son unas 20 comparaciones porque 2²⁰ ≈ 10⁶; eso es exactamente lo que significa O(log n).

La implementación (con sus dos trampas)

// devuelve una posición donde está x, o -1 si no está (a debe venir ordenado)
int busqueda_binaria(const vector<int>& a, int x) {
    int l = 0, r = (int)a.size() - 1;
    while (l <= r) {
        int mitad = l + (r - l) / 2; // evita desbordar (l+r) cuando son grandes
        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;
}

(El const vector<int>& del parámetro significa “recibe el vector sin copiarlo, y prometo no modificarlo” — el detalle está en Punteros y referencias.)

Las trampas clásicas: (1) calcular (l+r)/2 puede desbordar con índices gigantes — l + (r-l)/2 no; (2) olvidar el +1/-1 al mover l o r produce ciclos infinitos. Y el requisito innegociable: el arreglo debe estar ordenado — de ahí el combo sort + búsqueda = O(n log n) total.

El invariante es: si x está, alguna aparición permanece en el intervalo cerrado [l,r]. Al descartar el medio lo excluimos con +1 o −1; así quedan menos candidatos.

Con {2,4,7}, buscar 5 visita [0,2] (medio 1, valor 4), luego [2,2] (valor 7) y termina en [2,1]: intervalo vacío, resultado −1. Buscar 2 conserva la mitad izquierda y devuelve 0; buscar 7 devuelve 2. En un vector vacío se inicia [0,−1]: el ciclo ni entra.

La versión STL

vector<int> a = {2, 4, 4, 7, 9};
// lower_bound: primer elemento >= x (el vector debe estar ordenado)
cout << (lower_bound(a.begin(), a.end(), 4) - a.begin()) << "\n"; // 1
cout << (lower_bound(a.begin(), a.end(), 5) - a.begin()) << "\n"; // 3
// binary_search: ¿está o no está?
cout << (binary_search(a.begin(), a.end(), 7) ? "SI" : "NO") << "\n";

El resultado de lower_bound es un iterador, una posición dentro del vector o su final. auto pide a C++ deducir ese tipo. Si it señala un elemento válido, *it lee su valor; it - a.begin() cuenta cuántas posiciones lo separan del inicio. end() señala justo después del último y no se puede leer.

Un uso que comprueba ambos requisitos antes de leer el iterador:

vector<int> a = {2, 4, 4, 7};
for (int x : {4, 5, 9}) {
    auto it = lower_bound(a.begin(), a.end(), x);
    int pos = (it != a.end() && *it == x) ? int(it - a.begin()) : -1;
    cout << pos << "\n"; // 1, -1, -1 en líneas separadas
}

&& evalúa de izquierda a derecha y se detiene si la primera condición es falsa. Eso evita intentar leer end().

lower_bound es la navaja suiza: además de buscar, responde “¿cuántos son menores que x?” (la posición que retorna). Su hermano upper_bound da el primer elemento estrictamente mayor.

El dibujo retoma el arreglo {2, 4, 4, 7, 9} del primer ejemplo STL. Las flechas señalan posiciones, no cantidades que haya que sumar.

2041427394lower_bound(4)primer elemento ≥ 4lower_bound(5) = upper_bound(4)primer elemento ≥ 5,que es también el primero > 4

Si el diagrama no cabe, deslízalo horizontalmente.

Con los dos se cuenta cuántas veces aparece un valor sin recorrer linealmente el rango: upper_bound(4) - lower_bound(4) es 3 − 1 = 2, y “cuántos hay entre 4 y 7 inclusive” es upper_bound(7) - lower_bound(4) = 4 − 1 = 3. Ese es el patrón que pide Paltas en la práctica.

Ejercicio de dedos (sin juez)

Lee n números y q consultas; para cada consulta responde la posición del valor o -1. Primero con tu implementación manual, después con lower_bound. Con repetidos, la búsqueda manual puede devolver cualquier aparición y lower_bound la primera: compara que ambas detecten presencia o ausencia, no que siempre devuelvan el mismo índice. Con lower_bound, comprueba que no sea end() y que el valor encontrado sea igual al buscado.

La ficha de referencia con todo esto junto —incluidos los idiomas de la STL para contar cuántos elementos caen en un rango— es Búsqueda binaria clásica.

En el módulo 12 esta herramienta se transforma en algo mucho más poderoso: buscar sobre la respuesta de un problema, no sobre un arreglo. La referencia completa del tema vive en Búsqueda Binaria.

🏋️ Práctica

Práctica directa: Buscar sin leer fuera del vector

En un vector ordenado {2,4,4,7}, responde la primera posición de cada consulta, o −1. Consultas: 4 5 9. Respuestas: 1 -1 -1.

Variación: Contar dentro de un intervalo

En un arreglo ordenado, responde cuántos valores están entre L y R, incluidos, con L ≤ R. Para {1,3,3,3,8}: [3,3] da 3; [4,7] da 0; [0,9] da 5. Considera también un arreglo vacío.

Aplicar en problemas

Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.

Problemas OCI reales, en español (cada nota trae el link a su mirror):

#ProblemaFaseQué practica
1BicicletaNacional 2016una búsqueda binaria por consulta
2PaltasRegional 2023contar en un rango con dos búsquedas
3⭐ La leyenda de ZoldaRegional 2017la K-ésima distancia, con enteros y sin flotantes

Más aplicaciones (en inglés)

#ProblemaDificultadQué practica
1Interesting drink (706B)★★ (1100)sort + una búsqueda por consulta
2Worms (474B)★★ (1200)acumular y buscar el rango
3⭐ Queries about less or equal elements (600B)★★★ (1300)upper_bound en masa

Un ejemplo para pensar

En {2, 4, 4, 7}, lower_bound busca el primer elemento mayor o igual al consultado. ¿Qué posiciones obtiene al consultar 4, 5 y 9? Las posiciones se cuentan desde cero.

Compara el código y predice su salida antes de ejecutarlo:

vector<int> a = {2, 4, 4, 7};
for (int x : {4, 5, 9}) {
    auto it = lower_bound(a.begin(), a.end(), x);
    cout << (it - a.begin()) << " ";
    // Primero comprueba el límite; solo después lee *it.
    bool esta = (it != a.end() && *it == x);
    cout << esta << "\n"; // bool se imprime como 1 o 0.
}

← 07 - Cuánto se demora tu programa · Ruta de Aprendizaje · 09 - Recursión →