binary_search
Les tests si un élément dans une plage trié qui est égale à une valeur spécifiée ou qui est équivalent à ce dernier dans une certaine mesure spécifié par un attribut binaire.
template<class ForwardIterator, class Type>
bool binary_search(
ForwardIterator _First,
ForwardIterator _Last,
const Type& _Val
);
template<class ForwardIterator, class Type, class BinaryPredicate>
bool binary_search(
ForwardIterator _First,
ForwardIterator _Last,
const Type& _Val,
BinaryPredicate _Comp
);
Paramètres
_First
Un itérateur vers l'avant adressant la position du premier élément dans la plage à rechercher._Last
Un itérateur vers l'avant adressant une position au delà de le dernier élément dans la plage à rechercher._Val
La valeur requise pour être mis en correspondance par la valeur de l'élément ou de qui doit respecter la condition à la valeur d'élément spécifié par l'attribut binaire._Comp
Objet défini par l'utilisateur de fonction de prédicat dans lequel définit le sens celles l'élément est inférieur des autres.Un attribut binaire accepte deux arguments et retourne truesi satisfaite et false une fois pas de contenu.
Valeur de retour
true si un élément est trouvé dans la plage qui est égal ou équivalent à la valeur spécifiée ; sinon, false.
Notes
La plage source triée référencé doit être valide ; tous les pointeurs doivent être deréférençables et, dans la séquence, la dernière position doit être accessible dès le début par l'augmentation.
L'intervalle trié chacun doit être organisé comme une condition préalable à l'application de l'algorithme d' binary_search conformément à la même chose qui classe qui est utilisée par l'algorithme pour trier les plages combinés.
Les plages sources ne sont pas modifiées par binary_search.
Les types valeur des itérateurs direct doivent être inférieur à comparable être ordonné, de sorte que, avec deux éléments, il puisse déterminer l'un ou l'autre qu'ils sont équivalents (dans le sens que ni l'un ni l'autre n'est inférieure à l'autre) ou qu'il est inférieure à l'autre.Cela provoque le 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 d'étapes proportionnelles à (_Last –_First).
Exemple
// alg_bin_srch.cpp
// compile with: /EHsc
#include <list>
#include <vector>
#include <algorithm>
#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> L;
list <int>::iterator Iter;
bool b1, b2;
L.push_back( 50 );
L.push_back( 10 );
L.push_back( 30 );
L.push_back( 20 );
L.push_back( 25 );
L.push_back( 5 );
L.sort( );
cout << "L = ( " ;
for ( Iter = L.begin( ) ; Iter != L.end( ) ; Iter++ )
cout << *Iter << " ";
cout << ")" << endl;
b1 = binary_search( L.begin( ), L.end( ), 10 );
if ( b1 )
cout << "There is an element in list L with a value equal to 10."
<< endl;
else
cout << "There is no element in list L with a value equal to 10."
<< endl;
// a binary_search under the binary predicate greater
L.sort ( greater<int> ( ) );
b2 = binary_search( L.begin( ), L.end( ), 10 , greater<int> ( ) );
if ( b2 )
cout << "There is an element in list L with a value equivalent to 10 "
<< "under greater than." << endl;
else
cout << "No element in list L with a value equivalent to 10 "
<< "under greater than." << endl;
// a binary_search under the user-defined binary predicate mod_lesser
vector <int> v1;
vector <int>::iterator Iter1;
int i;
for ( i = -2 ; i <= 4 ; i++ )
{
v1.push_back( i );
}
sort ( v1.begin ( ) , v1.end ( ) , mod_lesser );
cout << "Ordered under mod_lesser, vector v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
bool b3 = binary_search( v1.begin( ), v1.end( ), -3 , mod_lesser );
if ( b3 )
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;
}
Configuration requise
en-tête : <algorithm>
l'espace de noms : DST