# std::lower_bound() function with example in C++ STL

In this article, we are going to learn about the usage of the library function lower_bound() and how to use that?
Submitted by Radib Kar, on August 13, 2020

## std::lower_bound()

std::lower_bound() is an STL library function, which comes under the algorithm header library and finds the lower bound of the searching element in a range. Lower bound means the least element in the range which is greater or equal to the searching element.

Say the range is: [4, 5, 6, 9, 12] and the searching element is 6, then the lower bound is 6 itself. If the searching element is 7 then the lower bound would be 9

Cases:

1. When a searching element exists:
std::lower_bound() returns iterator to the element itself
2. When searching element doesn't exist:
1. If all elements are greater than the searching element:
lower_bound() returns an iterator to begin of the range.
2. If all elements are lower than the searching element:
lower_bound() returns an iterator to end of the range( No lower bound exists).
3. Otherwise,
lower_bound() returns an iterator to the next greater element to the search element(The closest element greater than the search element) of the range

To use the lower_bound() the range needs to be sorted.

Syntax:

```ForwardIterator lower_bound(
ForwardIterator first,
ForwardIterator last,
const T& searching_element
);
```

Parameter(s):

• ForwardIterator first: iterator to the start of the range
• ForwardIterator last: iterator to the end of the range
• const T& searching_element: T is the data type and searching_element is the element which lower bound is to be found

Return Type: The return type is an iterator to the lower bound found in the range.

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

int main()
{
vector<int> arr{ 6, 5, 9, 12, 4 };
//sort before using lower_bound()
sort(arr.begin(), arr.end());

int searching_element = 6;
vector<int>::iterator it;
it = lower_bound(arr.begin(), arr.end(), searching_element);

//if all eleemnts are smaller than the searching
//element then no lower bound exists
if (it == arr.end()) {
cout << "No lower bound exists\n";
}
else
cout << "Lower bound of " << searching_element << ": " << *it << endl;

searching_element = 7;

it = lower_bound(arr.begin(), arr.end(), searching_element);

//if all eleemnts are smaller than the searching
//element then no lower bound exists
if (it == arr.end()) {
cout << "No lower bound exists\n";
}
else
cout << "Lower bound of " << searching_element << ": " << *it << endl;

return 0;
}
```

Output:

```Lower bound of 6: 6
Lower bound of 7: 9
```

In the above lower_bound() function, to compare between elements default comparator operator '<' is used.

But we have an extended version function which uses a user-defined comparator to compare b/w elements.

```ForwardIterator lower_bound(
ForwardIterator first,
ForwardIterator last,
const T& searching_element,
Comparator comp);
```

Parameter(s):

• ForwardIterator first: iterator to the start of the range
• ForwardIterator last: iterator to the end of the range
• const T& searching_element: T is the data type and searching_element is the element which lower bound is to be found
• Comparator comp: user-defined comparator

Return type: The return type is an iterator to the lower bound found in the range.

This can be helpful if you have user-defined data types.

Preparation