Syntax:

#include <algorithm> forward_iterator lower_bound( forward_iterator first, forward_iterator last, const TYPE& val ); forward_iterator lower_bound( forward_iterator first, forward_iterator last, const TYPE& val, CompFn f );

The `lower_bound`

function is a type of binary search. This function searches
for the first place that `val`

can be inserted into the ordered range defined by
`first`

and `last`

that will not mess up the existing ordering; or,
equivalently, it returns the iterator to the first element that is not less than `val`

,
or `end`

if all elements are less than `val`

.

This function requires the elements to be in order.

The return value of `lower_bound`

is an iterator that points to the location
where `val`

can be safely inserted. Unless the comparison function `f`

is
specified, the `< operator`

is used for ordering.

For example, the following code uses `lower_bound`

to insert the number 7 into
an ordered vector of integers:

vector<int> nums; nums.push_back( -242 ); nums.push_back( -1 ); nums.push_back( 0 ); nums.push_back( 5 ); nums.push_back( 8 ); nums.push_back( 8 ); nums.push_back( 11 ); cout << "Before nums is: "; for( unsigned int i = 0; i < nums.size(); i++ ) { cout << nums[i] << " "; } cout << endl; vector<int>::iterator result; int new_val = 7; result = lower_bound( nums.begin(), nums.end(), new_val ); nums.insert( result, new_val ); cout << "After, nums is: "; for( unsigned int i = 0; i < nums.size(); i++ ) { cout << nums[i] << " "; } cout << endl;

The above code produces the following output:

Before nums is: -242 -1 0 5 8 8 11 After, nums is: -242 -1 0 5 7 8 8 11

`lower_bound`

runs in logarithmic time for containers that support random access, and in linear time for all other containers. It always makes O(log n) comparisons, though.

Related Topics: binary_search, equal_range, upper_bound