upper_bound


Category: algorithms	Component type: function

Prototype

Upper_bound is an overloaded name; there are actually two upper_bound functions.

template <class ForwardIterator, class LessThanComparable>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
                            const LessThanComparable& value);

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

Description

Upper_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last) [1]. Specifically, it returns the last position where value could be inserted without violating the ordering. [2] The first version of upper_bound uses operator< for comparison, and the second uses the function object comp.

The first version of upper_bound returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), value < *j is false.

The second version of upper_bound returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), comp(value, *j) is false.

Definition

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

Requirements on types

For the first version:

ForwardIterator is a model of Forward Iterator.
LessThanComparable is a model of LessThan Comparable.
The ordering on objects of type LessThanComparable is a strict weak ordering, as defined in the LessThan Comparable requirements.
ForwardIterator's value type is the same type as LessThanComparable.

For the second version:

ForwardIterator is a model of Forward Iterator.
StrictWeakOrdering is a model of Strict Weak Ordering.
ForwardIterator's value type is the same type as T.
ForwardIterator's value type is convertible to StrictWeakOrdering's argument type.

Preconditions

For the first version:

[first, last) is a valid range.
[first, last) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first, last) such that i precedes j, *j < *i is false.

For the second version:

[first, last) is a valid range.
[first, last) is ordered in ascending order according to the function object comp. That is, for every pair of iterators i and j in [first, last) such that i precedes j, comp(*j, *i) is false.

Complexity

The number of comparisons is logarithmic: at most log(last - first) + 1. If ForwardIterator is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to last - first. [3]

Example

int main()
{
  int A[] = { 1, 2, 3, 3, 3, 5, 8 };
  const int N = sizeof(A) / sizeof(int);

  for (int i = 1; i <= 10; ++i) {
    int* p = upper_bound(A, A + N, i);
    cout << "Searching for " << i << ".  ";
    cout << "Result: index = " << p - A << ", ";
    if (p != A + N)
      cout << "A[" << p - A << "] == " << *p << endl;
    else
      cout << "which is off-the-end." << endl;
  }
}

The output is:

Searching for 1.  Result: index = 1, A[1] == 2
Searching for 2.  Result: index = 2, A[2] == 3
Searching for 3.  Result: index = 5, A[5] == 5
Searching for 4.  Result: index = 5, A[5] == 5
Searching for 5.  Result: index = 6, A[6] == 8
Searching for 6.  Result: index = 6, A[6] == 8
Searching for 7.  Result: index = 6, A[6] == 8
Searching for 8.  Result: index = 7, which is off-the-end.
Searching for 9.  Result: index = 7, which is off-the-end.
Searching for 10.  Result: index = 7, which is off-the-end.

Notes

[1] Note that you may use an ordering that is a strict weak ordering but not a total ordering; that is, there might be values x and y such that x < y, x > y, and x == y are all false. (See the LessThan Comparable requirements for a more complete discussion.) Finding value in the range [first, last), then, doesn't mean finding an element that is equal to value but rather one that is equivalent to value: one that is neither greater than nor less than value. If you're using a total ordering, however (if you're using strcmp, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same.

[2] Note that even if an element that is equivalent to [1] value is already present in the range [first, last), the return value of upper_bound will not point to that element. The return value is either last or else an iterator i such that value < *i. If i is not equal to first, however, then *(i - 1) is less than or equivalent to value.

[3] This difference between Random Access Iterators and Forward Iterators is simply because advance is constant time for Random Access Iterators and linear time for Forward Iterators.

Using this site means you accept its terms of use \| privacy policy	\|	trademark information
Copyright © 1993-2003 Silicon Graphics, Inc. All rights reserved.	\|	contact us