Lower Bound y Upper Bound

¿Qué son lower y upper bound?

Imagina un estante de libros ordenados por precio. Quieres saber:

• Lower bound: ¿Dónde está el primer libro que cuesta al menos $50?
• Upper bound: ¿Dónde está el primer libro que cuesta más de $50?

Formalmente, en un arreglo ordenado:

• lower_bound(x) = posición del primer elemento ≥ x
• upper_bound(x) = posición del primer elemento > x

Usando las funciones de C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    //                 0  1  2  3  4  5  6  7  8
    vector<int> v = { 1, 2, 4, 4, 4, 6, 7, 8, 9 };

    // Lower bound de 4: primer elemento >= 4
    auto it1 = lower_bound(v.begin(), v.end(), 4);
    cout << "lower_bound(4) = índice " << (it1 - v.begin()) << endl;  // 2

    // Upper bound de 4: primer elemento > 4
    auto it2 = upper_bound(v.begin(), v.end(), 4);
    cout << "upper_bound(4) = índice " << (it2 - v.begin()) << endl;  // 5

    // Contar cuántos 4 hay
    cout << "Cantidad de 4's: " << (it2 - it1) << endl;  // 3

    // ¿Qué pasa si busco un número que no existe?
    auto it3 = lower_bound(v.begin(), v.end(), 5);
    cout << "lower_bound(5) = índice " << (it3 - v.begin()) << endl;  // 5 (apunta al 6)

    // Si el número es mayor que todos:
    auto it4 = lower_bound(v.begin(), v.end(), 100);
    cout << "lower_bound(100) = índice " << (it4 - v.begin()) << endl;  // 9 (v.end())

    return 0;
}

Implementación manual

Lower bound (primer elemento ≥ x)

int lowerBound(vector<int> &v, int x) {
    int lo = 0, hi = v.size();  // hi = n, no n-1

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (v[mid] < x) {
            lo = mid + 1;
        } else {
            hi = mid;       // v[mid] >= x, podría ser la respuesta
        }
    }

    return lo;  // Primer índice donde v[lo] >= x
}

Detalle clave: hi empieza en v.size() (no en v.size()-1) porque si todos los elementos son menores que x, la respuesta es n (posición después del último).

Upper bound (primer elemento > x)

int upperBound(vector<int> &v, int x) {
    int lo = 0, hi = v.size();

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (v[mid] <= x) {       // La única diferencia: <= en vez de <
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }

    return lo;  // Primer índice donde v[lo] > x
}

Tabla resumen visual

Arreglo: [1, 2, 4, 4, 4, 6, 7]

Aplicaciones comunes

1. Contar elementos en un rango [a, b]

int contarEnRango(vector<int> &v, int a, int b) {
    auto lo = lower_bound(v.begin(), v.end(), a);
    auto hi = upper_bound(v.begin(), v.end(), b);
    return hi - lo;
}
// contarEnRango(v, 3, 6) → cuenta cuántos elementos hay entre 3 y 6 inclusive

2. Verificar si un elemento existe

bool existe(vector<int> &v, int x) {
    auto it = lower_bound(v.begin(), v.end(), x);
    return it != v.end() && *it == x;
}

3. Encontrar el elemento más cercano

int masCercano(vector<int> &v, int x) {
    auto it = lower_bound(v.begin(), v.end(), x);

    if (it == v.end()) return v.back();
    if (it == v.begin()) return *it;

    // Comparar con el anterior
    auto prev_it = prev(it);
    if (x - *prev_it <= *it - x) return *prev_it;
    return *it;
}

4. Inserción manteniendo el orden

vector<int> v = {1, 3, 5, 7, 9};
int nuevo = 4;

auto pos = lower_bound(v.begin(), v.end(), nuevo);
v.insert(pos, nuevo);
// v = {1, 3, 4, 5, 7, 9}

Búsqueda binaria con comparadores personalizados

Puedes usar lower_bound con arreglos de structs:

struct Estudiante {
    string nombre;
    int calificacion;
};

bool porCalificacion(const Estudiante &a, int cal) {
    return a.calificacion < cal;
}

int main() {
    vector<Estudiante> estudiantes = {
        {"Ana", 70}, {"Luis", 80}, {"María", 85}, {"Pedro", 95}
    };

    // Primer estudiante con calificación >= 80
    auto it = lower_bound(estudiantes.begin(), estudiantes.end(), 80, porCalificacion);
    cout << it->nombre << endl;  // "Luis"
}

Ejercicios de práctica

Ejercicio 1

Dado un arreglo de N números enteros y Q consultas, cada consulta es un número X. Imprime cuántos elementos en el arreglo son estrictamente menores que X.

Ejemplo:

5
1 3 5 7 9
3
4 7 10

Salida: 2 3 5

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int &x : v) cin >> x;
    sort(v.begin(), v.end());

    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << (lower_bound(v.begin(), v.end(), x) - v.begin()) << " ";
    }
    cout << endl;

    return 0;
}

Ejercicio 2

Tienes un arreglo ordenado. Para cada consulta X, imprime el menor elemento ≥ X. Si no existe, imprime -1.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> v(n);
    for (int &x : v) cin >> x;
    sort(v.begin(), v.end());

    while (q--) {
        int x;
        cin >> x;
        auto it = lower_bound(v.begin(), v.end(), x);
        if (it == v.end()) {
            cout << -1 << endl;
        } else {
            cout << *it << endl;
        }
    }

    return 0;
}

Siguiente paso

Ahora que dominas la búsqueda en arreglos, aprende a buscar en grafos con BFS (búsqueda en amplitud).