The Standard C++ Library provides a number of different variations on binary search algorithms. All perform only approximately log n comparisons, where n is the number of elements in the range described by the arguments. The algorithms work best with random access iterators, like those generated by vectors or deques, when they also perform approximately log n operations in total. However, they also work with non-random access iterators, like those generated by lists, in which case they perform a linear number of steps. Although legal, it is not necessary to perform a binary search on a set or multiset data structure, since those container classes provide their own search methods, which are more efficient.
The generic algorithm binary_search() returns true if the sequence contains a value that is equivalent to the argument. Recall that to be equivalent means that both Compare(value, arg) and Compare(arg, value) are false. The algorithm is declared as follows:
bool binary_search (ForwardIterator first, ForwardIterator last,
const T & value [, Compare ] );
In other situations it is important to know the position of the matching value. This information is returned by a collection of algorithms, defined as follows:
ForwardIterator last, const T& value [ , Compare ] );
ForwardIterator upper_bound (ForwardIterator first,
ForwardIterator last, const T& value [, Compare ] );
pair<ForwardIterator, ForwardIterator> equal_range
(ForwardIterator first, ForwardIterator last,
const T& value [, Compare ] );
The algorithm lower_bound() returns, as an iterator, the first position into which the argument could be inserted without violating the ordering, whereas the algorithm upper_bound() finds the last such position. These match only when the element is not currently found in the sequence. Both can be executed together in the algorithm equal_range(), which returns a pair of iterators.
Our example program shows these functions being used with a vector of random integers.
void binary_search_example ()
// illustrates the use of the binary search algorithm
// see alg7.cpp for complete source code
{
// make an ordered vector of 15 random integers
vector<int> aVec(15);
generate (aVec.begin(), aVec.end(), randomValue);
sort (aVec.begin(), aVec.end());
// see if it contains an eleven
if (binary_search (aVec.begin(), aVec.end(), 11))
cout << "contains an 11" << endl;
else
cout << "does not contain an 11" << endl;
// insert an 11 and a 14
vector<int>::iterator where;
where = lower_bound (aVec.begin(), aVec.end(), 11);
aVec.insert (where, 11);
where = upper_bound (aVec.begin(), aVec.end(), 14);
aVec.insert (where, 14);
}