lower_bound() function in C++
Welcome to this tutorial. In this tutorial, we are going to learn about “How to use lower_bound() function in C++”.
The lower_bound algorithm is used to find the first location in a sorted sequence of values, or a specified range of values. The arguments are such that the sequence is sorted in ascending order.
- The “lower_bound()” function is a a built-in function in C++ Standard Template Library(STL). It returns an iterator pointing to the element which is equal to a given value or to the very first element which is greater than the given value from a sorted container.
- In order to use this function, you must include the following header file,
#include<algorithm>
- Syntax for a “lower_bound()” function is as follows,
lower_bound( starting_iterator , ending_iterator, value)
Here,
- the starting_iterator is an iterator that points to the first element of the container.
- the end_iterator is an iterator that points to the element which is just after the last element(and not the last element) of the container.
- the value is the constant value, the “lower_bound” of which is to be searched.
Working of lower_bound() function
- Case 1: If the value to be searched is smaller than the value of that in a sorted container then the lower_bound() will return an iterator pointing to the element which is just greater than the specified value.
- Case 2: If the value to be searched is equal to the element of the container then the lower_bound() will return an iterator pointing to that element.
- Case 3: If the value to be searched is greater than all the elements of the sorted container then the lower_bound() will return an iterator pointing to the “end” of the container which is generally ‘0’.
(Always remember that lower_bound() function will only work efficiently with sorted containers.)
Understanding lower_bound() function with an example
//C++ program that illustrates working of lower_bound() with vector #include<iostream> #include<algorithm> //Header file to include lower_bound() #include<vector> using namespace std; int main(void) { //Make sure that elements of the vector should be sorted //at the time of defining a vector vector<int> vec = {1, 5, 10, 15, 20, 25, 30}; //Here "auto it1" is the same as using //vector<int>::iterator it1 auto it1 = lower_bound(vec.begin(), vec.end(), 0); cout<<"Case 1: "<<(*it1)<<"\n"; it1 = lower_bound(vec.begin(), vec.end(), 10); cout<<"Case 2: "<<(*it1)<<"\n"; it1 = lower_bound(vec.begin(), vec.end(), 35); cout<<"Case 3: "<<(*it1)<<"\n"; return 0; }
The output of the above program
Case 1: 1 Case 2: 10 Case 3: 0
- Here, I had displayed the output based on the cases we discussed above.
- In “Case 1” you can see that when I tried to search lower_bound for an element(here ‘0’) then the lower_bound() function has return an iterator pointing to element just greater than the specified value. Hence the output is 1 here.
- Similarly for “Case 3”, the lower_bound function returns an iterator pointing to the end element(element after the last element) when I tried to search for an element greater than all the elements of the sorted vector.
- In “Case 2”, the value we are searching for is found in the vector which is why the lower_bound() function returns an iterator pointing to that element.
- Instead of “vectors”, you can also use “lower_bound()” function on arrays as well. There you just need to replace “vec.begin()” & “vec.end()” iterators with “array_name” & “array_name + number of elements in the array” respectively.
Thank you for reading this tutorial!!!
Comment down for any queries.
Leave a Reply