Previous fileTop of DocumentContentsIndex pageNext file
Apache C++ Standard Library User's Guide

14.4 Binary Search

The C++ Standard 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, such as those generated by vectors or deques. In this case they perform approximately log N operations in total. However, these algorithms also work with non-random access iterators, such as those generated by lists, in which case they perform a linear number of steps. Although possible, it is not worthwhile 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 std::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:

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:

The algorithm std::lower_bound() returns, as an iterator, the first position into which the argument could be inserted without violating the ordering, whereas the algorithm std::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 std::equal_range(), which returns a pair of iterators.

Our example program shows these functions being used with a vector of random integers.



Previous fileTop of DocumentContentsIndex pageNext file