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