.\" ident @(#)lower_bound.3
.\" Standard Template Library
.\" $$RW_INSERT_HEADER "slyrs.man"
.TH lower_bound 3C++ "02 Apr 1998" "Rogue Wave Software" "-"
.ce2
Standard C++ Library   
Copyright 1998, Rogue Wave Software, Inc.   

.SH NAME

\f2lower_bound\fP

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



.SH  SYNOPSIS


.br
template <class ForwardIterator, class T>
.br
ForwardIterator lower_bound(ForwardIterator first, 
.RE
.RS 28
ForwardIterator last,
.br
const T& value);
.RE
.RS 0

.br
template <class ForwardIterator, class T, class Compare>
.RE
.RS 1
ForwardIterator lower_bound(ForwardIterator first, 
.RE
.RS 29
ForwardIterator last,
.br
const T& value, Compare comp);



.SH  DESCRIPTION


The lower_bound algorithm compares a supplied \f2value\fP to elements in a sorted container and returns the first position in the container that \f2value\fP can occupy without violating the container's ordering. There are two versions of the algorithm. The first uses the less than operator (\f2operator<\fP) 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 \f2Compare\fP, and assumes that \f2Compare\fP 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 \f2value\fP, or, when the comparison operator is used, the first element that does not satisfy the comparison function. Formally, the algorithm returns an iterator \f2i\fP in the range \f2[first, last)\fP such that for any iterator \f2j\fP in the range \f2[first, i)\fP the following corresponding conditions hold: 

\f2*j  <  value\fP

or 

\f2comp(*j, value) == true\fP



.SH  COMPLEXITY


lower_bound performs at most \f2log(last - first) + 1\fP comparisons.



.SH  EXAMPLE



.RE
.RS 0
//
.br
// ul_bound.cpp
.br
//
.RE
.RS 1
#include <vector>
.br
#include <algorithm>
.br
#include <iostream>
.RE
.RS 0
using namespace std;
.RE
.RS 1

.RE
.RS 0
int main()
.RE
.RS 1
{
.RE
.RS 2
typedef vector<int>::iterator iterator;
.br
int d1[11] = {0,1,2,2,3,4,2,2,2,6,7};
.RE
.RS 0

.RE
.RS 3
// Set up a vector
.RE
.RS 2
vector<int> v1(d1,d1 + 11);
.RE
.RS 0

.RE
.RS 3
// Try lower_bound variants
.RE
.RS 2
iterator it1 = lower_bound(v1.begin(),v1.end(),3);
.RE
.RS 3
// it1 = v1.begin() + 4
.RE
.RS 0

.RE
.RS 2
iterator it2 = 
.RE
.RS 7
lower_bound(v1.begin(),v1.end(),2,less<int>());
.RE
.RS 3
// it2 = v1.begin() + 4
.RE
.RS 0

.RE
.RS 3
// Try upper_bound variants
.RE
.RS 2
iterator it3 = upper_bound(v1.begin(),v1.end(),3);
.RE
.RS 3
// it3 = vector + 5
.RE
.RS 0

.RE
.RS 2
iterator it4 = 
.RE
.RS 5
upper_bound(v1.begin(),v1.end(),2,less<int>());
.RE
.RS 3
// it4 = v1.begin() + 5 
.RE
.RS 0

.RE
.RS 2
cout << endl << endl
.RE
.RS 8
<< "The upper and lower bounds of 3: ( "
.br
<< *it1 << " , " << *it3 << " ]" << endl;
.RE
.RS 0

.RE
.RS 2
cout << endl << endl
.RE
.RS 8
<< "The upper and lower bounds of 2: ( "
.br
<< *it2 << " , " << *it4 << " ]" << endl;
.RE
.RS 0

.RE
.RS 2
return 0;
.RE
.RS 1
}

.br
.RE
.RS 0
Program Output



.RE
.RS 0

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



.SH  WARNINGS


If your compiler does not support default template parameters, then you always need to supply the \f2Allocator\fP template argument. For instance, you have to write:

\f2vector<int,allocator<int> >\fP

instead of:

\f2vector<int>\fP

If your compiler does not support namespaces, then you do not need the using declaration for \f2std\fP.



.SH  SEE ALSO


upper_bound, equal_range