std::lower_bound
From Cppreference
| Defined in header
<algorithm> | ||
| template< class ForwardIterator, class T >
ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last, | (1) | |
| template< class ForwardIterator, class T, class Compare >
ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last, | (2) | |
Returns an iterator pointing to the first element in the range [first, last) that is not less than value. The first version uses operator< to compare the elements, the second version uses the given comparison function comp.
Contents |
Parameters
| first, last | - | iterators defining the range to examine | |||||||||
| value | - | value to compare the elements to | |||||||||
| comp | - | comparison function which returns true if the first argument is less than the second. The signature of the comparison function should be equivalent to the following:
The signature does not need to have const &, but the function must not modify the objects passed to it. | |||||||||
Return value
iterator pointing to the first element that is not less than value, or last if no such element is found.
Complexity
logarithmic in the distance between first and last
Equivalent function
| First version: |
|---|
template<class ForwardIterator, class T> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value) { ForwardIterator it; std::iterator_traits<ForwardIterator>::distance_type count, step; count = distance(first,last); while (count > 0) { it = first; step = count/2; std::advance(it, step); if (!(value < *it)) { first = ++it; count -= step+1; } else count = step; } return first; } |
| Second version: |
template<class ForwardIterator, class T, class Compare> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp) { ForwardIterator it; std::iterator_traits<ForwardIterator>::distance_type count, step; count = distance(first,last); while (count > 0) { it = first; step = count/2; std::advance(it, step); if (!comp(value, *it)), first = ++it; count -= step+1; } else count = step; } return first; } |
Example
| This section is incomplete |
See also
| returns range of elements matching a specific key (function template) | |
| returns an iterator to the first element greater than a certain value (function template) | |
