# std::upper_bound

From cppreference.com
< cpp‎ | algorithm

Defined in header `<algorithm>` |  |
template< class ForwardIt, class T > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value ); | (1) |
template< class ForwardIt, class T, class Compare > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp ); | (2) |

Returns an iterator pointing to the first element in the range `[first, last)` that is greater than `value`.

The range `[first, last)` must be at least partially ordered, i.e. partitioned with respect to the expression !(value < element) or !comp(value, element). A fully-sorted range meets this criterion, as does a range resulting from a call to std::partition.

The first version uses operator< to compare the elements, the second version uses the given comparison function `comp`.

### Parameters

first, last | - | the range of elements to examine
value | - | value to compare the elements to

comp

-

comparison function object (i.e. an object that satisfies the requirements of `Compare`) which returns ​true if the first argument is less than the second.

The signature of the comparison function should be equivalent to the following:

bool cmp(const Type1 &a, const Type2 &b);

The signature does not need to have const &, but the function object 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 ForwardIt can be dereferenced and then implicitly converted to Type2. ​

Type requirements
- `ForwardIt` must meet the requirements of `ForwardIterator`.

### Return value

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

### Complexity

The number of comparisons performed is logarithmic in the distance between `first` and `last` (At most log
2(last - first) + O(1) comparisons). However, for non-`RandomAccessIterator`s, the number of iterator increments is linear.

### Possible implementation

First version

    template<class ForwardIt, class T>
    ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value)
    {
        ForwardIt it;
        typename std::iterator_traits<ForwardIt>::difference_type count, step;
        count = std::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 ForwardIt, class T, class Compare>
    ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
    {
        ForwardIt it;
        typename std::iterator_traits<ForwardIt>::difference_type count, step;
        count = std::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

Run this code

    #include <algorithm>
    #include <iostream>
    #include <iterator>
    #include <vector>

    int main()
    {
        std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };

        auto lower = std::lower_bound(data.begin(), data.end(), 4);
        auto upper = std::upper_bound(data.begin(), data.end(), 4);

        std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
    }

Output:

    4 4 4

### See also

equal_range | returns range of elements matching a specific key (function template)
lower_bound | returns an iterator to the first element not less than the given value (function template)
partition | divides a range of elements into two groups (function template)

Retrieved from "http://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/upper_bound&oldid=85654"