Namespaces
Variants

std:: binary_search

From cppreference.net
C++
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy , ranges::sort , ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17) (C++11)
(C++20) (C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
binary_search
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
Défini dans l'en-tête <algorithm>
(1)
template < class ForwardIt, class T >

bool binary_search ( ForwardIt first, ForwardIt last,

const T & value ) ;
(constexpr depuis C++20)
(jusqu'à C++26)
template < class ForwardIt, class T = typename std:: iterator_traits

< ForwardIt > :: value_type >
constexpr bool binary_search ( ForwardIt first, ForwardIt last,

const T & value ) ;
(depuis C++26)
(2)
template < class ForwardIt, class T, class Compare >

bool binary_search ( ForwardIt first, ForwardIt last,

const T & value, Compare comp ) ;
(constexpr depuis C++20)
(jusqu'à C++26)
template < class ForwardIt, class T = typename std:: iterator_traits

< ForwardIt > :: value_type ,
class Compare >
constexpr bool binary_search ( ForwardIt first, ForwardIt last,

const T & value, Compare comp ) ;
(depuis C++26)

Vérifie si un élément équivalent à value apparaît dans la partition de la plage [ first , last ) .

1) L'équivalence est vérifiée en utilisant operator < :

Si ! bool ( * iter < value ) && ! bool ( value < * iter ) est true pour un itérateur iter dans [ first , last ) , retourne true . Sinon retourne false .

Si l'une des conditions suivantes est satisfaite, le comportement est indéfini :

  • Pour tout élément elem de [ first , last ) , bool ( elem < value ) n'implique pas ! bool ( value < elem ) .
  • Les éléments elem de [ first , last ) ne sont pas partitionnés par rapport aux expressions bool ( elem < value ) et ! bool ( value < elem ) .
(jusqu'à C++20)

Équivalent à std :: binary_search ( first, last, value, std:: less { } ) .

(depuis C++20)
2) L'équivalence est vérifiée en utilisant comp :
Si ! bool ( comp ( * iter, value ) ) && ! bool ( comp ( value, * iter ) ) est true pour un itérateur iter dans [ first , last ) , retourne true . Sinon retourne false .
Si l'une des conditions suivantes est satisfaite, le comportement est indéfini :
  • Pour tout élément elem de [ first , last ) , bool ( comp ( elem, value ) ) n'implique pas ! bool ( comp ( value, elem ) ) .
  • Les éléments elem de [ first , last ) ne sont pas partitionnés par rapport aux expressions bool ( comp ( elem, value ) ) et ! bool ( comp ( value, elem ) ) .

Table des matières

Paramètres

first, last - la paire d'itérateurs définissant la plage partitionnée des éléments à examiner
value - valeur à comparer aux éléments
comp - prédicat binaire qui renvoie ​ true si le premier argument est ordonné avant le second.

La signature de la fonction de prédicat doit être équivalente à ce qui suit :

bool pred ( const Type1 & a, const Type2 & b ) ;

Bien que la signature n'ait pas besoin d'avoir const & , la fonction ne doit pas modifier les objets qui lui sont passés et doit pouvoir accepter toutes les valeurs de type (éventuellement const) Type1 et Type2 indépendamment de la catégorie de valeur (ainsi, Type1 & n'est pas autorisé , pas plus que Type1 sauf si pour Type1 un déplacement équivaut à une copie (depuis C++11) ).
Les types Type1 et Type2 doivent être tels qu'un objet de type T puisse être implicitement converti à la fois en Type1 et en Type2 , et qu'un objet de type ForwardIt puisse être déréférencé puis implicitement converti à la fois en Type1 et en Type2 . ​

Exigences de type
-
ForwardIt doit satisfaire aux exigences de LegacyForwardIterator .
-
Compare doit satisfaire aux exigences de BinaryPredicate . Il n'est pas requis de satisfaire Compare .

Valeur de retour

true si un élément équivalent à value est trouvé, false sinon.

Complexité

Étant donné N comme std:: distance ( first, last ) :

1) Au plus log 2 (N)+O(1) comparaisons avec value en utilisant operator < (jusqu'en C++20) std:: less { } (depuis C++20) .
2) Au plus log 2 (N)+O(1) applications du comparateur comp .

Cependant, si ForwardIt n'est pas un LegacyRandomAccessIterator , le nombre d'incrémentations d'itérateur est linéaire en N .

Notes

Bien que std::binary_search exige seulement que [ first , last ) soit partitionné, cet algorithme est généralement utilisé dans le cas où [ first , last ) est trié, de sorte que la recherche binaire soit valide pour toute value .

std::binary_search vérifie uniquement si un élément équivalent existe. Pour obtenir un itérateur vers cet élément (s'il existe), std::lower_bound devrait être utilisé à la place.

Macro de test de fonctionnalité Valeur Std Fonctionnalité
__cpp_lib_algorithm_default_value_type 202403 (C++26) Initialisation par liste pour les algorithmes ( 1,2 )

Implémentation possible

Voir également les implémentations dans libstdc++ et libc++ .

binary_search (1) 
template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type>
bool binary_search(ForwardIt first, ForwardIt last, const T& value)
{
    return std::binary_search(first, last, value, std::less{});
}
binary_search (2) 
template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type,
         class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    first = std::lower_bound(first, last, value, comp);
    return (!(first == last) and !(comp(value, *first)));
}

Exemple

Exécuter ce code 
#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <vector>
int main()
{
    const auto haystack = {1, 3, 4, 5, 9};
    for (const auto needle : {1, 2, 3})
    {
        std::cout << "Recherche de " << needle << '\n';
        if (std::binary_search(haystack.begin(), haystack.end(), needle))
            std::cout << "Trouvé " << needle << '\n';
        else
            std::cout << "Non trouvé !\n";
    }
    using CD = std::complex<double>;
    std::vector<CD> nums{{1, 1}, {2, 3}, {4, 2}, {4, 3}};
    auto cmpz = [](CD x, CD y){ return abs(x) < abs(y); };
    #ifdef __cpp_lib_algorithm_default_value_type
        assert(std::binary_search(nums.cbegin(), nums.cend(), {4, 2}, cmpz));
    #else
        assert(std::binary_search(nums.cbegin(), nums.cend(), CD{4, 2}, cmpz));
    #endif
}

Sortie : 

Recherche de 1
Trouvé 1
Recherche de 2
Non trouvé !
Recherche de 3
Trouvé 3

Rapports de défauts

Les rapports de défauts modifiant le comportement suivants ont été appliqués rétroactivement aux normes C++ précédemment publiées.

DR Appliqué à Comportement publié Comportement corrigé
LWG 270 C++98 Compare devait satisfaire Compare et T devait être
LessThanComparable (ordre faible strict requis) 		seul un partitionnement est requis ;
comparaisons hétérogènes autorisées
LWG 787 C++98 au maximum log 2 (N)+2 comparaisons étaient autorisées corrigé en log 2 (N)+O(1)

Voir aussi

retourne la plage d'éléments correspondant à une clé spécifique
(modèle de fonction)
retourne un itérateur vers le premier élément non inférieur à la valeur donnée
(modèle de fonction)
retourne un itérateur vers le premier élément supérieur à une certaine valeur
(modèle de fonction)
(C++20)
détermine si un élément existe dans une plage partiellement ordonnée
(objet fonction algorithme)