1.
Introduction
2.
What is lower_bound() in C++?
3.
Syntax of lower_bound C++ Algorithm
3.1.
Syntax 1:
3.2.
Syntax 2:
4.
Parameters of lower_bound C++ Algorithm
5.
Return Value of lower bound C++ Algorithm
6.
Time Complexity of lower_bound C++ Algorithm
7.
Data races of lower_bound C++ Algorithm
8.
Exceptions of lower_bound C++ Algorithm
9.
How Does lower_bound C++ Algorithm Work?
10.
Examples of Lower bound in C++
10.1.
Example 1
10.1.1.
Code
10.2.
C++
10.2.1.

10.2.2.
Output:
10.2.3.
Explanation:
10.3.
Example 2
10.3.1.
Code
10.4.
C++
10.4.1.

10.4.2.
Output:
10.4.3.
Explanation:
10.5.
Example 3
10.5.1.
Code:
10.6.
C++
10.6.1.

10.6.2.
Output:
10.6.3.
Explanation:
10.7.
Example 4
10.7.1.
Code:
10.8.
C++
10.8.1.

10.8.2.
Output:
10.8.3.
Explanation:
11.
11.1.
What is the use of lower bound in C++?
11.2.
What is an example of a lower bound?
11.3.
Can we use lower bound on array in C++?
11.4.
What is another name for lower bound in function?
11.5.
What is the difference between upper_bound and lower_bound in C++?
12.
Conclusion
Last Updated: Mar 28, 2024
Easy

Lower Bound in C++

Sajid Khan
1 upvote
Basics of C++
Free guided path
9 chapters
99+ problems

Introduction

In this article, we will take a look at the lower_bound() in C++ method. We will also briefly see the upper_bound method in C++ and the uses of both of these methods.

What is lower_bound() in C++?

The lower_bound() in C++ is a built-in STL method that returns an iterator to the first value in a sorted array or vector that is not less than the key (the parameter passed in the method). If a number equals to the key, it returns an iterator pointing to that value. If there are multiple occurrences of the value that is equal to the key, then it returns the iterator pointing to the first occurrence of the value.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Syntax of lower_bound C++ Algorithm

Syntax 1:

Default

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

Syntax 2:

With Comparator

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

Parameters of lower_bound C++ Algorithm

The Following parameters are used in the lower_bound() in C++

• first: it is the iterator that points to the first element in the search space.
• last: it is the iterator that points to the last element in the search space.
• val: it is the value whose lower bound we are searching in the search space.
• comp: it is an optional parameter. It is a user-defined boolean function that takes two parameters and return true if they are in order or false otherwise.

Return Value of lower bound C++ Algorithm

The return value of the lower_bound() in C++ function is an iterator that points to the lower bound of the val. If no elements greater than or equal to val, it returns an iterator to the last element of the array or vector.

Time Complexity of lower_bound C++ Algorithm

The time complexity of the lower_bound() in C++ method is O(log2N), where N is the number of elements in the search space.

Data races of lower_bound C++ Algorithm

None of the types of variables modifies the content of the container. Hence, there are no data races and it can be used concurrently.

Exceptions of lower_bound C++ Algorithm

In C++, some of the exceptions that can occur in lower-bound functions include:

1. std::bad_alloc: Thrown when memory allocation fails.
2. std::out_of_range: Thrown when an attempt is made to access an element outside the valid range of a container.
3. std::invalid_argument: Thrown when an invalid argument is passed to a function.
4. std::length_error: Thrown when a container exceeds its maximum allowed size.
5. std::logic_error: Thrown when a function is called with invalid arguments or when a program is in an invalid state.
6. std::runtime_error: Thrown when an error occurs during program execution that is not related to a logical error or invalid arguments.

How Does lower_bound C++ Algorithm Work?

In C++, the lower_bound algorithm is used to search for the position of a specified value in a sorted sequence, like a vector or an array. The algorithm returns an iterator pointing to the first element in the range that is not less than the given value.

Here's how it works step by step:

Step 1: The lower_bound algorithm requires the sequence to be sorted in ascending order. This means that all the elements should be arranged from the smallest to the most significant value.

Step 2: Specify the range to search for the value. It takes two iterators: the first points to the beginning of the range and the second points just beyond the end of the range.

Step 3:  The lower_bound algorithm uses a binary search technique to find the position of the value efficiently.

Step 4:  The algorithm compares the value in the middle of the current range with the target value. If the middle value is less than the target value, the target value must be in the right half of the current range. If the middle value is greater than or equal to the target value, the target value must be in the left half of the current range.

Step 6: The binary search updates the range based on the comparison results.

Step 7: When the search is complete, the lower_bound algorithm returns an iterator pointing to the first element in the range that is not less than the given value.

Examples of Lower bound in C++

• C++

C++

``#include <bits/stdc++.h>using namespace std;int main(){vector<int> arr = {2, 4, 6, 8, 10, 11}; // vectorint pos1, pos2, pos3; // positions of the lower_boundsauto it1 = lower_bound(arr.begin(), arr.end(), 10); //iteratorpos1 = (it1-arr.begin());auto it2 = lower_bound(arr.begin(), arr.end(), 12); //iteratorpos2 = (it2-arr.begin());auto it3 = lower_bound(arr.begin(), arr.end(), 7); //iteratorpos3 = (it3-arr.begin());cout << "The value is: << *it1 <<" at index: "<< pos1<< endl;cout << "The value is: << *it2 <<" at index: "<< pos2<< endl;cout << "The value is: << *it3 <<" at index: "<< pos3<< endl;return 0;}``

Output:

``````The value is: 10 at index: 4
The value is: 1041 at index: 6
The value is: 8 at index: 3``````

Explanation:

• In the first output, we are searching for the value 10, and 10 is present in the vector, so it returns a pointer to the index containing 10, which is 4.
• In the second output, we are searching for the value 12, and we don’t have any value greater than or equal to 12. So, it returns a pointer to index 6, which is 1 more than the last index, and the value is a garbage value.
• In the third output, we are searching for the value 7, and we have an 8, which is greater than 7. So, it returns a pointer pointing to index 3 containing 8.

• C++

C++

``#include <iostream>#include <algorithm>int main() {    int arr[] = {1, 2, 2, 3, 4, 5};    int n = sizeof(arr) / sizeof(arr[0]);    // Find the first occurrence of the value 2    int* it = std::lower_bound(arr, arr + n, 2);    // Check if the value was found    if (it != arr + n && *it == 2) {        std::cout << "Found at index " << it - arr << '\n';    } else {        std::cout << "Not found\n";    }    return 0;}``

Output:

``Found at index 1``

Explanation:

In this example, lower_bound is used to find the first occurrence of the value 2 in the sorted array arr. The function returns an iterator pointing to the first element that is not less than 2, which in this case is the second element (the first occurrence of 2). The code then checks if the iterator points to the end of the range or if the value was actually found and prints a message accordingly.

• C++

C++

``#include <iostream>#include <algorithm>#include <vector>int main() {  std::vector<int> nums = {1, 3, 5, 7, 9};  // Find the position of the first element that is greater than or equal to 4  auto it = std::lower_bound(nums.begin(), nums.end(), 4);  if (it != nums.end()) {    std::cout << "The element at position " << std::distance(nums.begin(), it)              << " is " << *it << std::endl;  } else {    std::cout << "The element was not found." << std::endl;  }  return 0;}``

Output:

``The element at position 2 is 5``

You can practice by yourself with the help of Online C++ Compiler for better understanding.

Explanation:

In this example, we create a vector nums containing some sorted integers. We then use std::lower_bound to find the position of the first element in the vector that is greater than or equal to the value 4. The lower_bound function returns an iterator to the found element or to the end of the vector if the element is not found. We then use std::distance to get the position of the found element in the vector and output it along with the element value.

• C++

C++

``#include <iostream>#include <vector>#include <algorithm>int main() {    std::vector<int> v = {1, 3, 5, 7, 9};    // Insert the value 4 in the vector at the correct position    auto it = std::lower_bound(v.begin(), v.end(), 4);    v.insert(it, 4);    // Print the contents of the vector    for (int x : v) {        std::cout << x << ' ';    }    std::cout << '\n';    return 0;}``

Output:

``1 3 4 5 7 9``

Explanation:

In this example, lower_bound is used to find the insertion position of the value 4 in the sorted vector v. The function returns an iterator pointing to the first element that is not less than 4, which in this case is the element with value 5. The code then inserts the value 4 at that position using the insert function of the vector. Finally, the contents of the vector are printed to verify that the value was inserted in the correct position.

What is the use of lower bound in C++?

The lower_bound function in C++ is used to find the first element in a sorted range that is not less than a given value. It is commonly used to perform binary search on sorted containers like arrays and vectors.

What is an example of a lower bound?

An example of a lower bound is the minimum acceptable value in a given range. For instance, if a dataset has a lower bound of 0, any value below 0 would violate the lower bound constraint.

Can we use lower bound on array in C++?

Yes, in C++, the lower_bound function can be used on an array to obtain an iterator pointing to the first element not less than a specified value.

What is another name for lower bound in function?

Another name for std::lower_bound function in C++ is "binary search". It performs a binary search on a sorted range of elements to find the first element that is greater than or equal to a specified value.

What is the difference between upper_bound and lower_bound in C++?

In c++, lower_bound gives an iterator to the first element not less than the value. upper_bound returns an iterator to the first element greater than the value. Both are used with sorted collections. If the value isn't in the range, they both give the same position.

Conclusion

In this article we looked into the working of upper_bound() and lower_bound() in C++, we also learned about the time complexity of both the methods and saw examples of what output is produced by both these methods in different scenarios.