# binary_search

**Visual Studio 2012**

Tests whether there is an element in a sorted range that is equal to a specified value or that is equivalent to it in a sense specified by a binary predicate.

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 );

The sorted source range referenced must be valid; all pointers must be dereferenceable and, within the sequence, the last position must be reachable from the first by incrementation.

The sorted range must each be arranged as a precondition to the application of the **binary_search** algorithm in accordance with the same ordering as is to be used by the algorithm to sort the combined ranges.

The source ranges are not modified by **binary_search**.

The value types of the forward iterators need to be less-than comparable to be ordered, so that, given two elements, it may be determined either that they are equivalent (in the sense that neither is less than the other) or that one is less than the other. This results in an ordering between the nonequivalent elements

The complexity of the algorithm is logarithmic for random-access iterators and linear otherwise, with the number of steps proportional to (_Last –* *_First).

// 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; }

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