• http://facebook.com/
• https://www.google.com/accounts/o8/id
• https://me.yahoo.com

# upper_bound

Finds the first element greater than a given value

## Definition

The upper_bound() algorithm is defined in the standard header <algorithm> and in the nonstandard backward-compatibility header <algo.h>.

## Interface

```#include <algorithm>
template < class ForwardIterator, class Type >
ForwardIterator upper_bound(
ForwardIterator first,
ForwardIterator last,
const Type& val
);
template < class ForwardIterator, class Type, class Predicate >
ForwardIterator upper_bound(
ForwardIterator first,
ForwardIterator last,
const Type& val,
Predicate comp
);```

Parameters:
Parameter Description
first The position of the first element in the range to be searched
last The position one past the final element in the range to be searched
val The value in the ordered range that needs to be exceeded by the value of the element addressed by the iterator returned
comp User-defined predicate function object that defines sense in which one element is less than another. A binary predicate takes two arguments and returns `true` when satisfied and `false` when not satisfied

## Description

Upper_bound algorithm is a version of binary search: it attempts to find the element `val` in an ordered range `[first, last)`.

The first version uses `operator<` for comparison and the second uses the function object `comp`.

## Return Value

Returns an iterator adressing the position of the first element that has a value grater than or equal to `val`.

## Complexity

The complexity is logarithmic in the distance between `first` and `last`.

### References

Example:
##### Example - upper_bound algorithm
Problem
This program illustrates the use of the STL upper_bound() algorithm (default version) to find the upper bound location of a given target value in a vector of integers sorted in ascending order
Workings
```#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
int a[] = {2, 3, 5, 6, 7, 7, 7,  8, 9, 10};
vector<int> v(a, a+10);
cout <<"\nHere are the contents of v:\n";
for (vector<int>::size_type i=0; i<v.size(); i++)
cout <<v.at(i)<<" ";

vector<int>::iterator upper;

upper = upper_bound(v.begin(), v.end(), 3);
if (upper != v.end())
cout <<"\nUpper bound of 3 in v = "<<*upper;

upper = upper_bound(v.begin(), v.end(), 4);
if (upper != v.end())
cout <<"\nUpper bound of 4 in v = "<<*upper;

upper = upper_bound(v.begin(), v.end(), 5);
if (upper != v.end())
cout <<"\nUpper bound of 5 in v = "<<*upper;

upper = upper_bound(v.begin(), v.end(), 7);
if (upper != v.end())
cout <<"\nUpper bound of 7 in v = "<<*upper;

upper = upper_bound(v.begin(), v.end(), 0);
if (upper != v.end())
cout <<"\nUpper bound of 0 in v = "<<*upper;

upper = upper_bound(v.begin(), v.end(), 15);
if (upper != v.end())
cout <<"\nUpper bound of 15 in v = "<<*upper;
cout <<"\nNote that the upper bound location of 15 is \nthe end (one-past-the-last) vector
position.";

return 0;
}```
Solution
Output:

Here are the contents of v:
2 3 5 6 7 7 7 8 9 10

Upper bound of 3 in v = 5

Upper bound of 4 in v = 5

Upper bound of 5 in v = 6

Upper bound of 7 in v = 8

Upper bound of 0 in v = 2

Note that the upper bound location of 15 is
the end (one-past-the-last) vector position.
References