C++ Algorithm lower_bound()

Syntax of lower_bound C++ Algorithm

Syntax of normal lower_bound():

Syntax of lower_bound() with comparator:

Parameters of lower_bound C++ Algorithm

From the syntax, we can see that we have 4 parameters:

1. first: It is a pointer used to define the starting of the search space. We start from the exact point where the first is pointing.
2. last: It is a pointer used to define the ending of the search space. We do not include it in the search space.
3. val: This is of the type of array or vector elements. It is the value we want to search through the search space.
4. comp: This function returns a boolean value. It has 2 parameters as input of the same type as the array or vector elements. It is used to compare those variables. It is not necessary to use this parameter.

Return Value of lower bound C++ Algorithm

The lower_bound() function returns a pointer of the type, the same as an array or vector elements. If no elements are greater than or equal to the val, then the lower_bound() function returns the pointer to last. (It does not check if the last is fulfilling the conditions or not).

Exceptions of lower_bound C++ Algorithm

Exceptions are thrown by the lower_bound() function in C++ when there is some exception thrown by the comparator (default or custom), or it can also be thrown when some invalid operations on the iterator of the lower_bound() function are done. An example of an exception that might be thrown can be when we have a custom comparator that compares values by dividing and throws the Divide by Zero Arithmetic error. An example of the same is discussed later in this article.

How Does lower_bound C++ Algorithm Work?

The lower_bound() function in C++ uses the Binary Search technique, and so it needs that the search space is sorted. The search space should be sorted in ascending order for the default comparator. Let us see the algorithm used to implement the lower_bound() in C++:

Algorithm:

• Define 2 pointers, first and last, first pointing to the first element of the search space and last pointing to the last element which is not included in the search space. (These are passed as parameters).

• Define the middle pointer, which is at the half of the first and last, and len, which is simply the difference between the last and first.

• Run a loop while len is not zero.

• Inside the loop, change the middle value to (last + first)/2.

  • Here we have 2 cases:
    • if the value at the middle is less than val, then changefirsttomiddle+1 and decrement len by ( len /2 - 1).
    • else change the value of last to middle and len to len /2.

• At last, we return the pointer first.

Time Complexity: Worst case time complexity of lower_bound() is $O(log_{2} N)$. At every step, the search space is halved. Since the search space is getting halved, let's say that we require no more k steps, after which $N/2^k$ becomes 1. So the time complexity comes out to be the number of steps (i.e., k), which is $O(log_{2} N)$.

Examples

Let us understand lower_bound() function in C++ better using some examples:

Example 1

Let Us Start With a Simple Case. Let Us Say We Have An Integer Vector in Ascending Order, and We Will Try to Find a Just Greater Number.

Code:

Output:

Explanation: Since we have the value 9 present in the vector, we are getting it as the output.

Example 2

Let Us See How we can print the Position of The Result of the lower_bound()

Code:

Output:

Explanation: Here, we have used the difference of iterators pointing to the lower_bound() and the first element. It gives us the index in 0 based since, let us say that the first element is the answer, then the output will be 0.

Example 3

Let us Say that We do not Have an Element That is Greater Than or Equal to The Value Passed. Let Us See What it Will Print.

Code:

Output:

Explanation: Since no element is greater than 11, we are getting a garbage value and the index 1 more than the end index. To avoid these issues, we generally handle this case separately. (It will be shown in the next example).

Example 4

Let Us Say Our Search Space is Sorted in Descending order, now Sorting it in Ascending Order Can be 1 Approach to Use lower_bound(), but That Will Take O(NlogN) Time Complexity. So Let Us Try to Use a Custom Comparator.

Code:

Output:

Explanation: Since we have the search space sorted in descending order, we are using the greater() function of C++. The greater function compares 2 elements based on greater than inequality. Now, since we can see that the next smaller element of 8 is 7, the output is 7.

Example 5

Now Let Us Say The Vector Elements are Not Sorted. Let Us Sort Them and Then Use the lower_bound() Function.

Code:

Output:

Explanation: Here, we first sort the vector in ascending order, then use the lower_bound() function to search through the vector.

Example 6

Let Us Try to Throw An Exception in The lower_bound() Function Using a Custom Comparator.

Code:

Output:

Explanation: Since the custom comparator divides a number by 0, we are getting a Math error in the output. We can overcome this by ensuring no exceptions in the comparator.

Read More:

• Vector in C++.