upper_bound


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

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

Return iterator to upper bound

Returns an iterator pointing to the first element in the sorted range [first,last) which compares greater than value. The comparison is done using either operator< for the first version, or comp for the second.

For the function to yield the expected result, the elements in the range shall already be ordered according to the same criterion (operator< or comp).

Unlike lower_bound, this function does not return an iterator to the element if it compares equivalent to value, but only if it compares strictly greater.

The behavior of this function template is equivalent to:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
template <class ForwardIterator, class T>
  ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last, const T& value )
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::distance_type count, step;
  count = distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; advance (it,step);
    if (!(value<*it))                 // or: if (!comp(value,*it)), for the comp version
      { first=++it; count-=step+1;  }
    else count=step;
  }
  return first;
}


Parameters

first, last
Input iterators to the initial and final positions of the sequence to use. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
value
Element value to be checked for its upper bound.
comp
Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.


Return value

Iterator to the upper bound position for value in the range.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
// lower_bound/upper_bound example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20
  vector<int>::iterator low,up;

  sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

  low=lower_bound (v.begin(), v.end(), 20); //          ^
  up= upper_bound (v.begin(), v.end(), 20); //                   ^

  cout << "lower_bound at position " << int(low- v.begin()) << endl;
  cout << "upper_bound at position " << int(up - v.begin()) << endl;

  return 0;
}


Output:
lower_bound at position 3
upper_bound at position 6


Complexity

At most, logarithmic number of comparisons and linear number of steps in the length of [first,last).
If used with random-access iterators, number of steps is reduced to logarithmic.

See also

lower_bound Return iterator to lower bound (function template)
equal_range Get subrange of equal elements (function template)
binary_search Test if value exists in sorted array (function template)
max_element Return largest element in range (function template)