# C++ <algorithm> - lower_bound() Function

The C++ algorithm::lower_bound function returns an iterator pointing to the first element in the range [first,last) which does not compare less than the specified value. The elements are compared using operator< (in first version) or comp (in second version). The elements in the range should be already sorted using the same criterion (operator< or comp), or at least partitioned with respect to specified value.

### Syntax

```//default version
template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first,
ForwardIterator last,
const T& val);

//custom version
template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound (ForwardIterator first,
ForwardIterator last,
const T& val,
Compare comp);
```

### Parameters

 `first` Specify initial position of the forward iterator of a sorted (or properly partitioned) sequence. The range used is [first,last). `last` Specify final position of the forward iterator of a sorted (or properly partitioned) sequence. The range used is [first,last). `val` Specify the value of the lower bound to be searched for in the range. `comp` Specify a binary function that accepts two element as argument (one element from the range as first, and val as second), and returns a value convertible to bool. The returned value indicates whether the first argument is considered to go before the second.

### Return Value

Returns an iterator to the lower bound of the specified value or last if all elements of the range is compared less than the specified value.

### Time Complexity

On Average, Logarithmic i.e, Θ(log(n)).

### Example:

In the example below, the algorithm::lower_bound function is used to find out the lower bound of the specified value in the given range.

```#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main (){
vector<int> vec= {10, 60, 50, 30, 40, 20};
vector<int>::iterator up, low;

//sorting the vector
sort(vec.begin(), vec.end());

//upper and lower bound for 30 in vec
low = lower_bound(vec.begin(), vec.end(), 30);
up = upper_bound(vec.begin(), vec.end(), 30);

cout<<"Lower bound for 30 in vec: "<<*low<<".\n";
cout<<"Upper bound for 30 in vec: "<<*up<<".\n";

return 0;
}
```

The output of the above code will be:

```Lower bound for 30 in vec: 30.
Upper bound for 30 in vec: 40.
```

### Example:

The example below shows how to use comp with algorithm::lower_bound function.

```#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool less_than (int i, int j) {
return (i<j);
}

int main (){
vector<int> vec= {10, 60, 50, 30, 40, 20};
vector<int>::iterator up, low;

//sorting the vector
sort(vec.begin(), vec.end());

//upper and lower bound for 50 in vec
low = lower_bound(vec.begin(), vec.end(), 50, less_than);
up = upper_bound(vec.begin(), vec.end(), 50, less_than);

cout<<"Lower bound for 50 in vec: "<<*low<<".\n";
cout<<"Upper bound for 50 in vec: "<<*up<<".\n";

return 0;
}
```

The output of the above code will be:

```Lower bound for 50 in vec: 50.
Upper bound for 50 in vec: 60.
```

❮ C++ <algorithm> Library

5