The lower_bound in C++
In this tutorial, we are going to learn the concept of lower_bound in C++. Initially, we discuss what is lower_bound method is in C++, then its syntax, parameters and return value. Finally, we provide a few examples to understand the topic better. Without delay, let's dive into the concept.
What is lower_bound in C++?
In C++, the lower_bound() method locates the first occurrence of a particular value in its sorted container. It is a C++ library that does binary search on arrays, vectors, and other sorted containers as part of the algorithm> library. The lower_bound() method creates an iterator pointing to the initial element in a container's defined range that is not less than the supplied value.
Syntax:
template <class Forward_Iterator, class T>
Forward_Iterator lower_bound(Forward_Iterator first, Forward_Iterator last,
const T& val);
template <class Forward_Iterator, class T, class Compare>
Forward_Iterator lower_bound(Forward_Iterator first, Forward_Iterator last,
const T& val, Compare comp);
Lower_bound C++ Algorithm Parameters
The syntax reveals that we have four parameters:
- first: It is the pointer that specifies where the search space begins. We begin exactly where the first point is pointing.
- last: This is a pointer that indicates where the search space ends. It is not in the field of search space.
- val: This is an array or vector element. We need to search the search space for the value.
- comp: This function gives a boolean result. It takes two parameters of the same kind as an array or vector items as input. It compares those variables. This parameter is optional.
Lower_bound C++ Algorithm Exceptions
In C++, exceptions are raised by the lower_bound() method when an exception is raised by the comparator (either custom or default) or when improper actions are performed on the function's iterator. An instance of an exception that could occur is if we have a custom comparator that divides values for comparison and raises the Divide by Zero Arithmetic Error.
What is the lower_bound C++ Algorithm?
The lower_bound() method in C++ employs the Binary Search method, which necessitates sorting the search space. For the default comparator, sort the search space in ascending order. Let's explore the algorithm used to create lower_bound() in C++:
Algorithm:
- Create the two pointers, the first and the last, using the first referencing to the first element within the search space and the last pointing to the last element not within the search space. (The above are passed as arguments).
- Create the middle pointer, a point located halfway between the first and last points, and len, which signifies the distinction between the first and last points.
- Run a loop as long as len is not 0.
- Modify the middle value within the loop to (last + first)/2.
- There are two possibilities here: if the value in the middle is lower than val, changefirsttomiddle+1 along with decrement len by (len /2 - 1).
- Otherwise, change final to middle and len to len /2.
- Finally, the pointer is returned first.
- Lower_bound() has a worst-case time complexity of (2)O(log 2N). The search space is half at each phase. Because the search space is halving, let's pretend we don't need any more k steps, at which point /2N/2 becomes 1. As a result, the temporal complexity is the total number of steps (i.e., k), which is (2)O(log 2N).
Return Value
Lower_bound() creates an iterator pointing to an initial element equal to or greater than the val. If every element included in a container's declared range is smaller than the value given val, the lower_bound() method returns an iterator pointing to the range's last element; otherwise, it returns an iterator pointing to the range's starting element.
Examples of lower_bound in C++:
Example 1:
Code:
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> vec = {11, 32, 15, 27, 9, 10};
auto itr = lower_bound(vec.begin(), vec.end(), 9);
cout << "Value is: " << *itr << endl;
return 0;
}
Output:
![The lower_bound in C++](https://static.tutorialandexample.com/cpp/the-lower-bound-in-cpp1.png)
Example 2:
Code:
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> vec = {11, 13, 15, 17, 19, 10};
auto itr = lower_bound(vec.begin(), vec.end(), 15);
int pos = (itr - vec.begin());
cout << "Value is: " << *itr << " at the position: " << pos << endl;
return 0;
}
Output:
![The lower_bound in C++](https://static.tutorialandexample.com/cpp/the-lower-bound-in-cpp2.png)
Example 3:
Code:
#include <bits/stdc++.h>
using namespace std;
int main() {
// given vector
vector<int> vec = {12, 13, 15, 17, 19, 20};
// Iterator
auto itr = lower_bound(vec.begin(), vec.end(), 21);
int pos = (itr - vec.begin());
// Printing the value and position
cout << "Value is: " << *itr << " at the position: " << pos << endl;
return 0;
}
Output:
![The lower_bound in C++](https://static.tutorialandexample.com/cpp/the-lower-bound-in-cpp3.png)
Example 4:
Code:
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> vec = {10, 19, 17, 15, 13, 11};
auto itr = lower_bound(vec.begin(), vec.end(), 18, greater<int>());
int pos = (itr - vec.begin());
// Checking if the element exists or not.
if(itr == vec.end())
cout<<"The element does not Exist"<<endl;
else
// Displaying the value and position.
cout << "Value is: " << *itr << " at the position: " << pos << endl;
return 0;
}
Output:
![The lower_bound in C++](https://static.tutorialandexample.com/cpp/the-lower-bound-in-cpp4.png)
Conclusion
- The lower_bound() function refers to the first element whose value is equal to or greater than the value provided.
- The lower_bound() method searches the space using binary search.
- The search space does not contain the last value given as a lower_bound() function parameter. The value returns the last pointer if it has no larger than or equal elements.
- Lower_bound() allows for the advantage of the custom comparator.
- Worst-case Scenario: The lower_bound() function has a time complexity of ( ) O(logN).
- Lower_bound() is a ( 1 ) O(1) space operation because it doesn't use any extra space.