I have forgotten
my Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttps://me.yahoo.com

lower_bound

Finds the first element greater than or equal to a given value
+ View version details

Definition

The lower_bound() algorithm is defined in the standard header <algorithm> and in the nonstandard backward-compatibility header <algo.h>.

Interface

#include <algorithm>
template < class ForwardIterator, class Type >
   ForwardIterator lower_bound(
      ForwardIterator first, 
      ForwardIterator last,
      const Type& val
   );
template < class ForwardIterator, class Type, class BinaryPredicate >
   ForwardIterator lower_bound(
      ForwardIterator first, 
      ForwardIterator last,
      const Type& val,
      BinaryPredicate comp
   );

Parameters:
Parameter Description
first A forward iterator addressing the position of the first element in the range to be searched
last A forward iterator addressing the position one past the final element in the range to be searched
val The value whose first position or possible first position is being searched for in the ordered range
comp User-defined predicate function object that defines sense in which one element is less than another. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied

Description

Lower_bound algorithm is a version of binary search: it attempts to find the element val in an ordered range [first, last).

The first version uses operator< for comparison and the second uses the function object comp.

Return Value

Returns an iterator adressing the position of the first element that has a value less than or equal to val.

Complexity

The complexity is logarithmic in the distance between first and last.
Example:

Example - lower_bound algorithm
Problem
This program illustrates the use of the STL lower_bound() algorithm (default version) to find the lower bound location of a given target value in a vector of integers sorted in ascending order.
Workings
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
  int a[] = {2, 3, 5, 6, 7, 7, 7,  8, 9, 10};
  vector<int> v(a, a+10);
  cout <<"\nHere are the contents of v:\n";
  for (vector<int>::size_type i=0; i<v.size(); i++)
    cout <<v.at(i)<<" ";
 
  vector<int>::iterator lower;
 
  lower = lower_bound(v.begin(), v.end(), 3);
  if (lower != v.end())
    cout <<"\nLower bound of 3 in v = "<<*lower;
 
  lower = lower_bound(v.begin(), v.end(), 4);
  if (lower != v.end())
    cout <<"\nLower bound of 4 in v = "<<*lower;
 
  lower = lower_bound(v.begin(), v.end(), 5);
  if (lower != v.end())
    cout <<"\nLower bound of 5 in v = "<<*lower;
 
  lower = lower_bound(v.begin(), v.end(), 7);
  if (lower != v.end())
    cout <<"\nLower bound of 7 in v = "<<*lower;
  cout <<"\nThis is the first of the three 7's, since the value before this 7 is "
       <<*(lower-1)<<".";
 
  lower = lower_bound(v.begin(), v.end(), 0);
  if (lower != v.end())
    cout <<"\nLower bound of 0 in v = "<<*lower;
 
  lower = lower_bound(v.begin(), v.end(), 15);
  if (lower != v.end())
    cout <<"\nLower bound of 15 in v = "<<*lower;
  cout <<"\nNote that the lower bound location of 15 is \nthe end (one-past-the-last) vector
position.";
 
  return 0;
}
Solution
Output:

Here are the contents of v:
2 3 5 6 7 7 7 8 9 10

Lower bound of 3 in v = 3

Lower bound of 4 in v = 5

Lower bound of 5 in v = 5

Lower bound of 7 in v = 7
This is the first of the three 7's, since the value before this 7 is 6.

Lower bound of 0 in v = 2

Note that the lower bound location of 15 is
the end (one-past-the-last) vector position.
References