C++ <algorithm> - upper_bound() Function

The C++ algorithm::upper_bound function returns an iterator pointing to the first element in the range [first,last) which compares greater than the specified value. The elements are compared using operator< (in first version) or comp (in second version). The elements in the range should be already sorted using the same criterion (operator< or comp), or at least partitioned with respect to specified value.

Syntax

//default version
template <class ForwardIterator, class T>
   ForwardIterator upper_bound (ForwardIterator first, 
                                ForwardIterator last,
                                const T& val);

//custom version
template <class ForwardIterator, class T, class Compare>
  ForwardIterator upper_bound (ForwardIterator first, 
                               ForwardIterator last,
                               const T& val, 
                               Compare comp);

Parameters

`first`	Specify initial position of the forward iterator of a sorted (or properly partitioned) sequence. The range used is [first,last).
`last`	Specify final position of the forward iterator of a sorted (or properly partitioned) sequence. The range used is [first,last).
`val`	Specify the value of the upper bound to be searched for in the range.
`comp`	Specify a binary function that accepts two element as argument (one element from the range as first, and val as second), and returns a value convertible to bool. The returned value indicates whether the first argument is considered to go before the second.

Return Value

Returns an iterator to the upper bound of the specified value or last if all elements of the range is compared greater than the specified value.

Time Complexity

On Average, Logarithmic i.e, Θ(log(n)).

Example:

In the example below, the algorithm::upper_bound function is used to find out the upper bound of the specified value in the given range.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main (){
  vector<int> vec= {10, 60, 50, 30, 40, 20};
  vector<int>::iterator up, low;

  //sorting the vector
  sort(vec.begin(), vec.end());

  //upper and lower bound for 30 in vec
  low = lower_bound(vec.begin(), vec.end(), 30);
  up = upper_bound(vec.begin(), vec.end(), 30);

  cout<<"Lower bound for 30 in vec: "<<*low<<".\n";
  cout<<"Upper bound for 30 in vec: "<<*up<<".\n";

  return 0;
}

The output of the above code will be:

Lower bound for 30 in vec: 30.
Upper bound for 30 in vec: 40.

Example:

The example below shows how to use comp with algorithm::upper_bound function.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool less_than (int i, int j) {
  return (i<j);
}

int main (){
  vector<int> vec= {10, 60, 50, 30, 40, 20};
  vector<int>::iterator up, low;

  //sorting the vector
  sort(vec.begin(), vec.end());

  //upper and lower bound for 50 in vec
  low = lower_bound(vec.begin(), vec.end(), 50, less_than);
  up = upper_bound(vec.begin(), vec.end(), 50, less_than);

  cout<<"Lower bound for 50 in vec: "<<*low<<".\n";
  cout<<"Upper bound for 50 in vec: "<<*up<<".\n";

  return 0;
}

The output of the above code will be:

Lower bound for 50 in vec: 50.
Upper bound for 50 in vec: 60.

❮ C++ <algorithm> Library