Login
lower_bound
Finds the first element greater than or equal to a given value
Key Facts
Gyroscopic Couple: The rate of change of angular momentum (= Moment of Inertia.
= Angular velocity
= Angular velocity of precession.
Blaise Pascal (1623-1662) was a French mathematician, physicist, inventor, writer and Catholic philosopher.
Leonhard Euler (1707-1783) was a pioneering Swiss mathematician and physicist.
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 elementval 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 toval.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.
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