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.