## lower_bound

    Algorithm

- Summary
- Data Type and Member Function Indexes
- Synopsis
- Description
- Complexity
- Example
- Warnings
- See Also

### Summary

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

### Data Type and Member Function Indexes
(exclusive of constructors and destructors)

None

### 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>
     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 parameters, 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

Copyright (c) 1998, Rogue Wave Software, Inc.
Send mail to report errors or comment on the documentation.
OEM Release, June 1998