Standard C++	Library
 		 Copyright 1996, Rogue Wave Software, Inc.

 NAME

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

 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 part 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 <iostream.h>

   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,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;
    }

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

 WARNING

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

   vector<int, allocator<int> >

   instead of :

   vector<int>

 SEE ALSO

   lower_bound, equal_range

 STANDARDS CONFORMANCE
   ANSI X3J16/ISO WG21 Joint C++	Committee