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.
Si el diagrama no cabe, deslízalo horizontalmente.
| Paso | Intervalo de índices | Medio y valor | Decisión |
|---|---|---|---|
| 1 | [0, 7] | 3 → 7 | 7 < 9: seguir en [4, 7] |
| 2 | [4, 7] | 5 → 12 | 12 > 9: seguir en [4, 4] |
| 3 | [4, 4] | 4 → 9 | Encontrado 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]:
| Necesidad | Herramienta | Resultado para x = 4 |
|---|---|---|
| Saber si existe | binary_search | true |
| Primera posición con valor ≥ x | lower_bound | índice 1 |
| Primera posición con valor > x | upper_bound | índice 3 |
| Contar apariciones | restar esos dos iteradores | 2 |
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.