std::lower_bound

From Cppreference

Jump to: navigation, search

Defined in header `<algorithm>`

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

template< class ForwardIterator, class T, class Compare > ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last, const T& value, Compare comp );	(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.

The signature does not need to have const &, but the function must not modify the objects passed to it.
The type Type1 must be such that an object of type T can be implicitly converted to Type1. The type Type2 must be such that an object of type ForwardIterator can be dereferenced and then implicitly converted to Type2.

[edit] Return value

iterator pointing to the first element that is not less than value, or last if no such element is found.

[edit] Complexity

logarithmic in the distance between first and last

[edit] 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 = std::distance(first, last);
 
    while (count > 0) {
        it = first; 
        step = count / 2; 
        std::advance(it, step);
        if (*it < value) {
            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 = std::distance(first,last);
 
    while (count > 0) {
        it = first;
        step = count / 2;
        std::advance(it, step);
        if (comp(*it, value)),
            first = ++it;
            count -= step + 1;
        } else count = step;
    }
    return first;
}

[edit] Example

[edit] See also

equal_range

returns range of elements matching a specific key
(function template)

upper_bound

returns an iterator to the first element greater than a certain value
(function template)