lower_bound

10,000+ views

GPL — licence
Edit / fork this page
Contents
  1. Definition
  2. Interface
  3. Description
  4. Return Value
  5. Complexity
  6. References
  7. See Also

Finds the first element greater than or equal to a given value

You're viewing an older version of this page (#4166). View the current version.

Computing Stl Algorithms Binarysearch

View versions (1)

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:

ParameterDescription
firstA forward iterator addressing the position of the first element in the range to be searched
lastA forward iterator addressing the position one past the final element in the range to be searched
valThe value whose first position or possible first position is being searched for in the ordered range
compUser-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.

References

Example 1
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

See Also