binary_search
Testet, ob ein Element in einem sortierten Bereich gibt, der gleich einem angegebenen Wert ist, oder, der darauf auf eine Weise entspricht, durch ein binäres Prädikat angegeben hat.
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
);
Parameter
_First
Ein Vorwärtsiterator, der die Position des ersten Elements im Bereich behandelt gefunden werden._Last
Ein Vorwärtsiterator, der die Position eine hinter dem letzten Element im Bereich behandelt gefunden werden._Val
Der Wert, der erforderlich ist, durch den Wert des Elements oder des dessen verglichen werden sollen, muss die Bedingung mit dem Elementwert erfüllen, der durch das binäre Prädikat angegeben wird._Comp
Benutzerdefiniertes Prädikatfunktionsobjekt, dem Sinne definiert, in dem ein Element kleiner als andere.Ein binäres Prädikat verwendet zwei Argumente und gibt zurück , wenn true erfüllt und false, wenn nicht erfüllt wird.
Rückgabewert
true, wenn ein Element im Bereich gefunden wird, der gleich oder den angegebenen Wert entspricht; andernfalls false.
Hinweise
Der sortierte Quellbereich, auf den verwiesen wird, muss gültig sein; alle Zeiger müssen dereferenzierbar sein, und in der Sequenz, muss die letzte Position von der ersten durch Zunahme erreichbar sein.
Der sortierte Bereich muss jedes als Vorbedingung zur Verwendung des binary_search Algorithmus in Übereinstimmung mit der Reihenfolge angeordnet werden, wie, durch den Algorithmus verwendet werden, um das Sortieren der kombinierten Bereiche ist.
Die Quellbereiche werden nicht von binary_search geändert.
Die Werttypen der Vorwärtsiteratoren müssen weniger-als vergleichbar sein, sortiert werden, sodass, zwei Elemente angegeben wurde, es jedem bestimmt werden kann, dass sie äquivalent sind (insofern, dass kein kleiner ist als die andere ist), oder dass ein kleiner als das andere ist.Dies ergibt eine Reihenfolge zwischen den Elementen antivalenten
Die Komplexität des Algorithmus ist logarithmisch für Iteratoren mit wahlfreier Zugriff und andernfalls, mit der Anzahl der Schritte linear, die proportional zu sind (_Last -_First).
Beispiel
// 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;
}
Anforderungen
Header: <algorithm>
Namespace: std