lower_bound

  #include <algorithm>
  iterator lower_bound( iterator first, iterator last,  const TYPE& val );
  iterator lower_bound( iterator first, 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.

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