# lower_bound

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

## 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`

.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