Recover Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttp://yahoo.com/
advanced search

Valid RSS

Computing › Stl › Algorithms › Binarysearch ›

upper_bound

Finds the first element greater than a given value
+ View version details
Contents
  1. Definition
  2. Interface
  3. Description
  4. Return Value
  5. Complexity
  6. Page Comments

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

See Also

Last Modified: 2012-01-07 18:57:48     Page Rendered: 2012-05-22 16:43:57
 

Page Comments

 
 Format Excel Equations

  You must login to leave a messge