lower_bound

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