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
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.