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:
- std::bad_alloc: Thrown when memory allocation fails.
- std::out_of_range: Thrown when an attempt is made to access an element outside the valid range of a container.
- std::invalid_argument: Thrown when an invalid argument is passed to a function.
- std::length_error: Thrown when a container exceeds its maximum allowed size.
- std::logic_error: Thrown when a function is called with invalid arguments or when a program is in an invalid state.
- 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++
Example 1
Code
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> arr = {2, 4, 6, 8, 10, 11}; // vector
int pos1, pos2, pos3; // positions of the lower_bounds
auto it1 = lower_bound(arr.begin(), arr.end(), 10); //iterator
pos1 = (it1-arr.begin());
auto it2 = lower_bound(arr.begin(), arr.end(), 12); //iterator
pos2 = (it2-arr.begin());
auto it3 = lower_bound(arr.begin(), arr.end(), 7); //iterator
pos3 = (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;
}
You can also try this code with Online C++ Compiler
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.
Example 2
Code
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;
}
You can also try this code with Online C++ Compiler
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.
Example 3
Code:
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;
}
You can also try this code with Online C++ Compiler
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.
Example 4
Code:
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;
}
You can also try this code with Online C++ Compiler
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.
Frequently Asked Questions
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.
Recommended reading:
27+ registered 
