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_boundybinary_searchde 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:
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.
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.
Idea para comprobar tu solución
lower_bound devuelve posiciones 1,3,4. Solo la primera contiene el valor pedido; 4 es end y no se puede leer.
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.
Una pista, si la necesitas
Busca dos fronteras que encierren todas las repeticiones.
Contrastar el razonamiento
La respuesta es la posición del primer valor mayor que R menos la del primero mayor o igual que L:
upper_bound(R) − lower_bound(L). Ambas pueden ser el final; no necesitas desreferenciarlas.
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):
| # | Problema | Fase | Qué practica |
|---|---|---|---|
| 1 | Bicicleta | Nacional 2016 | una búsqueda binaria por consulta |
| 2 | Paltas | Regional 2023 | contar en un rango con dos búsquedas |
| 3 | ⭐ La leyenda de Zolda | Regional 2017 | la K-ésima distancia, con enteros y sin flotantes |
Más aplicaciones (en inglés)
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Interesting drink (706B) | ★★ (1100) | sort + una búsqueda por consulta |
| 2 | Worms (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.
}Una posición de inserción no prueba que el valor exista
Obtiene 1, 3 y 4. Para 4 señala su primera aparición; para 5 señala el 7; para 9 devuelve
end(), cuya distancia al inicio es el tamaño del arreglo. Para comprobar presencia hay que verificar primero que el resultado no seaend()y después que su valor sea el buscado. No se puede leer un elemento en la posición 4 de este arreglo.
← 07 - Cuánto se demora tu programa · Ruta de Aprendizaje · 09 - Recursión →