CKTIS / C++
std::lower_bound — première position non inférieure à une clé
std::lower_bound recherche la limite d’une plage partitionnée comme il convient : le premier élément qui n’est pas inférieur à la clé, ou la fin de la plage. Elle renvoie un itérateur, et non la confirmation qu’une valeur égale existe.
Version : C++23; repository compiler flag, production runtime not attested
Syntaxe
#include <algorithm>
std::lower_bound(first, last, value)
std::lower_bound(first, last, value, comp)std::lower_bound, déclarée dans <algorithm>, recherche dans [first, last) et renvoie le premier itérateur pour lequel comp(*it, value) est faux, ou last si aucun élément de ce type n’existe. Sans comp, elle utilise la comparaison par défaut « inférieur à ». Dans une plage numérique croissante, le résultat désigne le premier élément >= value, y compris le premier doublon.
La précondition est que la plage soit partitionnée pour la clé considérée : tous les éléments satisfaisant comp(element, value) doivent précéder les autres. Un tri complet selon la même comparaison suffit, mais n’est pas nécessaire. Le non-respect de cette condition entraîne un comportement indéfini ; la fonction ne trie pas les données.
Le résultat ne confirme pas que la clé existe. Vérifiez it != last avant d’utiliser *it. Dans l’exemple avec des entiers, le code vérifie seulement it != values.end() avant d’afficher la valeur candidate ; il ne la compare pas à la clé. Une fois la fin de la plage écartée, vous pouvez tester séparément l’égalité avec *it == key. Pour un ordre personnalisé, l’équivalence signifie !comp(a, b) && !comp(b, a), et pas nécessairement a == b.
Il faut au minimum des itérateurs de catégorie forward. Pour N éléments, le nombre de comparaisons est O(log N), mais sans itérateurs à accès aléatoire, le nombre de pas d’itérateur peut être linéaire. L’exemple vise C++23 ; le document lié est un projet de travail évolutif, et non une édition figée de C++23.
Exemples
#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';
}
}
Résultat
3: index=1, value=3 4: index=3, value=7 9: index=4, end
Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.