binary_search

Article
06/09/2015

Teste si un élément dans une plage triée est égal à une valeur spécifiée ou lui est équivalent d'une manière spécifiée par un prédicat binaire.

template<class ForwardIterator, class Type> 
   bool binary_search( 
      ForwardIterator first,  
      ForwardIterator last, 
      const Type& value 
   ); 
template<class ForwardIterator, class Type, class BinaryPredicate> 
   bool binary_search( 
      ForwardIterator first,  
      ForwardIterator last, 
      const Type& value,  
      BinaryPredicate comp 
   );

Paramètres

first
Un itérateur forward qui adresse la position du premier élément dans la plage de recherche.
last
Un itérateur forward qui adresse la position un après l'élément final dans la plage de recherche.
value
La valeur requise pour être mise en correspondance par la valeur de l'élément ou qui doit respecter la condition avec la valeur d'élément spécifiée par le prédicat binaire.
comp
Objet de fonction de prédicat défini par l'utilisateur qui définit le sens dans lequel un élément est inférieur à un autre. Un prédicat binaire a besoin de deux arguments. Il renvoie truelorsqu'il est satisfait et false dans le cas contraire.

Valeur de retour

true si un élément est trouvé dans la plage qui est égale ou équivalente à la valeur spécifiée ; sinon, false.

Notes

La plage source triée référencée doit être valide ; tous les pointeurs doivent être deréférençables et, dans la séquence, la dernière position doit être accessible à partir de la première par incrémentation.

Les plages triées doivent chacune être organisée comme une condition préalable à l'application de l'algorithme binary_search conformément au même critère de classement à être utilisé par l'algorithme pour trier les plages associées.

Les plages sources ne sont pas modifiées par binary_search.

Les types de valeur des itérateurs avancés ne doivent pas être inférieurs à comparable pour être classés, afin que, avec deux éléments, il puisse être possible de déterminer si l'un ou l'autre est équivalent (dans le sens où aucune n'est inférieur à l'autre) ou que l''un est inférieur à l'autre. Cela entraîne un classement entre les éléments d'inégalité

La complexité de l'algorithme est logarithmique pour les itérateurs d'accès aléatoire et linéaire sinon, avec le nombre des étapes proportionnelles à (last - first).

Exemple

// alg_bin_srch.cpp
// compile with: /EHsc
#include <list>
#include <vector>
#include <algorithm>
#include <functional>      // greater<int>( )
#include <iostream>

// Return whether modulus of elem1 is less than modulus of elem2
bool mod_lesser( int elem1, int elem2 )
{
    if (elem1 < 0)
        elem1 = - elem1;
    if (elem2 < 0)
        elem2 = - elem2;
    return elem1 < elem2;
}

int main( )
{
    using namespace std;

    list <int> List1;

    List1.push_back( 50 );
    List1.push_back( 10 );
    List1.push_back( 30 );
    List1.push_back( 20 );
    List1.push_back( 25 );
    List1.push_back( 5 );

    List1.sort();

    cout << "List1 = ( " ;
    for ( auto Iter : List1 )
        cout << Iter << " ";
    cout << ")" << endl;

    // default binary search for 10
    if( binary_search(List1.begin(), List1.end(), 10) )
        cout << "There is an element in list List1 with a value equal to 10."
        << endl;
    else
        cout << "There is no element in list List1 with a value equal to 10."
        << endl;

    // a binary_search under the binary predicate greater
    List1.sort(greater<int>());
    if( binary_search(List1.begin(), List1.end(), 10, greater<int>()) )
        cout << "There is an element in list List1 with a value greater than 10 "
        << "under greater than." << endl;
    else
        cout << "No element in list List1 with a value greater than 10 "
        << "under greater than." << endl;

    // a binary_search under the user-defined binary predicate mod_lesser
    vector<int> v1;

    for( auto i = -2; i <= 4; ++i )
    {
        v1.push_back(i);
    }

    sort(v1.begin(), v1.end(), mod_lesser);

    cout << "Ordered using mod_lesser, vector v1 = ( " ;
    for( auto Iter : v1 )
        cout << Iter << " ";
    cout << ")" << endl;

    if( binary_search(v1.begin(), v1.end(), -3, mod_lesser) )
        cout << "There is an element with a value equivalent to -3 "
        << "under mod_lesser." << endl;
    else
        cout << "There is not an element with a value equivalent to -3 "
        << "under mod_lesser." << endl;
}

Sortie

List1 = ( 5 10 20 25 30 50 )
There is an element in list List1 with a value equal to 10.
There is an element in list List1 with a value greater than 10 under greater than.
Ordered using mod_lesser, vector v1 = ( 0 -1 1 -2 2 3 4 )
There is an element with a value equivalent to -3 under mod_lesser.