Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

CKTIS / C++

std::lower_bound — primera posición que no es menor que una clave

std::lower_bound busca el límite de un rango particionado adecuadamente: el primer elemento que no es menor que la clave, o el final del rango. Devuelve un iterador, no confirma que exista un valor igual.

Versión: C++23; repository compiler flag, production runtime not attested

Sintaxis

#include <algorithm>
std::lower_bound(first, last, value)
std::lower_bound(first, last, value, comp)

std::lower_bound, declarada en <algorithm>, busca en [first, last) y devuelve el primer iterador para el que comp(*it, value) es falso, o last si no existe tal elemento. Si no se proporciona comp, usa la comparación predeterminada de menor que. En un rango numérico ascendente, el resultado apunta al primer elemento >= value, incluido el primer duplicado.

La precondición es que el rango esté particionado para la clave concreta: todos los elementos que cumplen comp(element, value) deben preceder a los demás. Ordenar completamente con la misma comparación es suficiente, pero no necesario. Si se incumple esta condición, el comportamiento es indefinido; la función no ordena los datos.

El resultado no confirma que la clave exista. Comprueba it != last antes de usar *it. En el ejemplo con enteros, el código solo comprueba it != values.end() antes de imprimir el valor candidato; no lo compara con la clave. Una vez descartado el final del rango, puedes comprobar la igualdad por separado con *it == key. Con un orden personalizado, equivalencia significa !comp(a, b) && !comp(b, a), y no necesariamente a == b.

Se requieren como mínimo iteradores hacia delante. Para N elementos, el número de comparaciones es O(log N), pero sin iteradores de acceso aleatorio, el número de pasos del iterador puede ser lineal. El ejemplo tiene como objetivo C++23; el documento enlazado es un borrador de trabajo en evolución, no una edición inmutable de C++23.

Ejemplos

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    const std::vector<int> values{1, 3, 3, 7};
    for (int key : {3, 4, 9}) {
        const auto it = std::lower_bound(values.begin(), values.end(), key);
        std::cout << key << ": index=" << (it - values.begin());
        if (it != values.end()) {
            std::cout << ", value=" << *it;
        } else {
            std::cout << ", end";
        }
        std::cout << '\n';
    }
}

Resultado

3: index=1, value=3
4: index=3, value=7
9: index=4, end

El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.

Fuentes