Standard C++ Library Copyright 1998, Rogue Wave Software, Inc.

binary_search- Performs a binary search for a value on a container.

#include <algorithm> template <class ForwardIterator, class T> bool binary_search(ForwardIterator first, ForwardIterator last, const T& value); template <class ForwardIterator, class T, class Compare> bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

The binary_search algorithm, like other related algorithms (equal_range, lower_bound and upper_bound) performs a binary search on ordered containers. All binary search algorithms have two versions. The first version uses the less than operator (operator<) to perform the comparison, and assumes that the sequence has been sorted using that operator. The second version allows you to include a function object of typeCompare, which it assumes was the function used to sort the sequence. The function object must be a binary predi- cate. The binary_search algorithm returnstrueif a sequence con- tains an element equivalent to the argumentvalue. The first version of binary_search returnstrueif the sequence con- tains at least one element that is equal to the search value. The second version of the binary_search algorithm returnstrueif the sequence contains at least one element that satisfies the conditions of the comparison function. Formally, binary_search returnstrueif there is an iteratoriin the range [first,last) that satisfies the correspond- ing conditions: !(*i<value) && !(value< *i) orcomp(*i,value) ==false&&comp(value, *i) ==false

binary_search performs at mostlog(last-first) +2com- parisons.

// // b_search.cpp // #include <vector> #include <algorithm> #include <iostream> using namespace std; int main() { typedef vector<int>::iterator iterator; int d1[10] = {0,1,2,2,3,4,2,2,6,7}; // // Set up a vector // vector<int> v1(d1,d1 + 10); // // Try binary_search variants // sort(v1.begin(),v1.end()); bool b1 = binary_search(v1.begin(),v1.end(),3); bool b2 = binary_search(v1.begin(),v1.end(),11,less<int>()); // // Output results // cout << "In the vector: "; copy(v1.begin(),v1.end(), ostream_iterator<int,char>(cout," ")); cout << endl << "The number 3 was " << (b1 ? "FOUND" : "NOT FOUND"); cout << endl << "The number 11 was " << (b2 ? "FOUND" : "NOT FOUND") << endl; return 0; } Program Output In the vector: 0 1 2 2 2 2 3 4 6 7 The number 3 was FOUND The number 11 was NOT FOUND

If your compiler does not support default template parame- ters, then you always need to supply theAllocatortemplate argument. For instance, you have to write:vector<int,allocator<int> > instead of:vector<int> If your compiler does not support namespaces, then you do not need the using declaration forstd.

equal_range, lower_bound, upper_bound