CKTIS / C++
std::binary_search : tester l’appartenance à une plage ordonnée
std::binary_search renvoie un booléen indiquant si une plage ordonnée contient un élément équivalent à la clé.
Version : C++23
Syntaxe
template<class ForwardIt, class T>
constexpr bool binary_search(ForwardIt first, ForwardIt last, const T& value);
template<class ForwardIt, class T, class Compare>
constexpr bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp);std::binary_search de <algorithm> examine [first, last) et renvoie true si un élément est équivalent à value selon le comparateur. Il ne donne ni position ni nombre de doublons ; utilise lower_bound ou equal_range pour cela.
La précondition est le partitionnement pour cette clé précise dans les deux sens de comparaison, avec asymétrie : si comp(e, value) est vrai, comp(value, e) doit être faux. Trier entièrement selon le même ordre cohérent est une condition suffisante sûre, mais non nécessaire pour une seule clé. La violation du partitionnement ou de l’asymétrie produit un comportement indéfini. Une plage vide renvoie false.
Le nombre de comparaisons est logarithmique. Avec des itérateurs à accès aléatoire, les déplacements le sont aussi ; les autres peuvent exiger un nombre linéaire d’incréments. Le comparateur doit définir un ordre cohérent sans modifier les éléments.
Exemples
#include <algorithm>
#include <array>
#include <iostream>
int main() {
const std::array values{1, 3, 5, 7};
std::cout << std::binary_search(values.begin(), values.end(), 5) << '\n';
}
Résultat
1
std::binary_search → 1