Man Page lower_bound.3

                       Standard C++ Library
             Copyright 1998, 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  ele-
     ments  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 algo-
     rithm. 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 func-
     tion 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. For-
     mally, 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 comparis-
     ons.

EXAMPLE

     //
     // ul_bound.cpp
     //
      #include <vector>
      #include <algorithm>
      #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,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  parame-
     ters,  then you always need to supply the Allocator template
     argument. For instance, you have 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

     upper_bound, equal_range