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

 NAME

   lower_bound  - Determine the first valid position for	an element in
   a sorted container.

 SYNOPSIS

   template <class ForwardIterator, class T>
   ForwardIterator lower_bound(ForwardIterator first,
 			      ForwardIterator last,
 			      const T& value);

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

 DESCRIPTION

   The lower_bound algorithm compares a supplied	value to elements in a
   sorted container and	returns	the first position in the container
   that value can occupy without violating the container's ordering.
   There are	two versions of the algorithm.  The first uses the
   less than operator (operator<) to perform the comparison, and
   assumes that the sequence	has been sorted	using that operator.
   The second version lets you 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.

   lower_bound's	return value is	the iterator for the first element in
   the container that is greater than or equal to value, or,	when
   the comparison operator is used, the	first element that does	not
   satisfy the	comparison function. Formally, the algorithm returns
   an iterator	i in the range [first, last)	such that for any
   iterator j in	the range [first, i) the following corresponding
   conditions hold:

   *j  <	 value

   or

   comp(*j,  value) == true

 COMPLEXITY

   lower_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'll have to write:

   vector<int,allocator<int> >

   instead of:

   vector<int>

 SEE ALSO

   upper_bound, equal_range

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