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,

1. the starting_iterator is an iterator that points to the first element of the container.
2. 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.
3. 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.