Find bounds for, or location of, a value in a sorted sequence

Source code

Declaration

template <class ForwardIterator, class T>
inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
                                   const T& value);

template <class ForwardIterator, class T, class Compare>
inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
                                   const T& value, Compare comp);

template <class ForwardIterator, class T>
inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
                                   const T& value);

template <class ForwardIterator, class T, class Compare>
inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
                                   const T& value, Compare comp);

template <class ForwardIterator, class T>
inline pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value);

template <class ForwardIterator, class T, class Compare>
inline pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value,
            Compare comp);

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

Description The lower_bound functions return an iterator i referring to the first position in the sorted sequence in the range [ first, last) into which value may be inserted while maintaining the sorted ordering.

The upper_bound functions return an iterator i referring to the last position in the sorted sequence in the range [ first, last) into which value may be inserted while maintaining the sorted ordering.

The equal_range functions return a pair of iterators i and j referring to the first and last positions in the sorted sequence in the range [ first, last) into which value may be inserted while maintaining the sorted ordering.

The binary_search function returns true (ie. a non-zero value) if value is in the sorted sequence in the range [ first, last) and false (ie. 0) otherwise. In the first function of each pair of functions, element comparisons are done using operator<, while in the second they are done using the function object comp .

Type requirements

• ForwardIterator must be at least a regular forward iterator .
• For lower_bound, Compare must be a function object type that provides int operator()(S, T), where S is the dereference type of ForwardIterator. For upper_bound, Compare must be a function object type that provides T operator()(T, S), where S is the dereference type of ForwardIterator. For equal_range, Compare must be a function object type that provides int operator()(S, S), where S is the dereference type of ForwardIterator. For binary_search, Compare must be a function object type that provides T operator()(T, S), where S is the dereference type of ForwardIterator.

Group Sorting and related operations.

Time complexity Linear.

For random access iterators, the number of steps will be logarithmic. Regardless of the type of iterator, the number of comparison operations will be logarithmic.

Space complexity Constant.

Mutative? No.

Example Select here to view the source code for the example.

Implementation Select here to view source code (Copyright (C) 1994, Hewlett-Packard Company) for this algorithm.