HP Integrity NonStop H-Series - Manual (Page 188)

Click on the banner to return to the user guide home page.
©Copyright 1996 Rogue Wave Software
Binary Search
The standard library provides a number of different variations on binary search algorithms. All
will 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, when they will also perform approximately log n
operations in total. However, they will also work with non-random access iterators, such as those
generated by lists, in which case they will 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 lower_bound (ForwardIterator first,
ForwardIterator last, const T& value [ , Compare ] );
ForwardIterator upper_bound (ForwardIterator first,
ForwardIterator last, const T& value [, Compare ] );
pair 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 will 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 ()