## upper_bound

    Algorithm

- Summary
- Data Type and Member Function Indexes
- Synopsis
- Description
- Complexity
- Example
- Warnings
- See Also

### Summary

Determines the last valid position for a value in a sorted container.

### Data Type and Member Function Indexes
(exclusive of constructors and destructors)

None

### Synopsis

    #include <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);

### Description

The upper_bound algorithm is one of a set of binary search algorithms. All of these algorithms perform binary searches on ordered containers. Each algorithm has two versions. The first version uses the less than operator (`operator<`) to perform the comparison, and assumes that the sequence has been sorted using that operator. The second version allows you to include a function object of type `Compare`, and assumes that `Compare` is the function used to sort the sequence. The function object must be a binary predicate.

The upper_bound algorithm finds the last position in a container that `value` can occupy without violating the container's ordering. upper_bound's return value is the iterator for the first element in the container that is greater than `value`, or, when the comparison operator is used, the first element that does NOT satisfy the comparison function. Because the algorithm is restricted to using the less than operator or the user-defined function to perform the search, upper_bound returns an iterator `i` in the range `[first, last)` such that for any iterator `j` in the range `[first, i)` the appropriate version of the following conditions holds:

`!(value < *j)`

or

`comp(value, *j) == false`

### Complexity

upper_bound performs at most `log(last - first) + 1` comparisons.

### Example

    //
    // ul_bound.cpp
    //
    #include <vector>
    #include <algorithm>
    #include <functional>
    #include <iostream>
    using namespace std;

    int main()
     {
    typedef vector<int>::iterator iterator;
    int d1[11] = {0,1,2,2,3,4,2,2,2,6,7};

    // Set up a vector
    vector<int> v1(d1 + 0,d1 + 11);

    // Try lower_bound variants
    iterator it1 = lower_bound(v1.begin(),v1.end(),3);
    // it1 = v1.begin() + 4

    iterator it2 =
       lower_bound(v1.begin(),v1.end(),2,less<int>());
    // it2 = v1.begin() + 4

    // Try upper_bound variants
    iterator it3 = upper_bound(v1.begin(),v1.end(),3);
    // it3 = vector + 5

    iterator it4 =
       upper_bound(v1.begin(),v1.end(),2,less<int>());
    // it4 = v1.begin() + 5
    cout << endl << endl
         << "The upper and lower bounds of 3: ( "
         << *it1 << " , " << *it3 << " ]" << endl;
    cout << endl << endl
         << "The upper and lower bounds of 2: ( "
         << *it2 << " , " << *it4 << " ]" << endl;
    return 0;
     }

Program Output

    The upper and lower bounds of 3: ( 3 , 4 ]
    The upper and lower bounds of 2: ( 2 , 3 ]

### Warnings

If your compiler does not support default template parameters, then you always need to supply the `Allocator` template argument. For instance, you need to write:

`vector<int, allocator<int> >`

instead of:

`vector<int>`

If your compiler does not support namespaces, then you do not need the using declaration for `std`.

### See Also

lower_bound, equal_range

Copyright (c) 1998, Rogue Wave Software, Inc.
Send mail to report errors or comment on the documentation.
OEM Release, June 1998