Lower bound in C++
In C++, the lower_bound function is used to find the first element in a sorted array that is greater than or equal to a given value.
Syntax
The syntax for the lower_bound function is as follows:
std::lower_bound(first, last, value);
Here, first and last are iterators that define the range of the array, and value is the value to be searched for. The function returns an iterator to the first element in the array that is greater than or equal to the given value. If no such element is found, the function returns the iterator last.
Example:
Let's consider an example to understand the lower_bound function more clearly.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int arr[] = {1, 3, 5, 7, 9, 11};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 6;
auto it = lower_bound(arr, arr + n, key);
if (it == arr + n) {
cout<< "The key " << key << " is greater than all elements of the array." <<endl;
}
else {
cout<< "The key " << key << " is present at position " << (it - arr) << " in the array." <<endl;
}
return 0;
}
Output:
The key 6 is present at position 3 in the array.
In the above example, we have an array arr of size n. We want to find the position of the first element in the array that is greater than or equal to the key 6. We use the lower_bound function to find the iterator to the first element that is greater than or equal to the key. If the iterator is equal to arr + n, it means that the key is greater than all elements of the array.
Example:
Now let's consider another example to understand the lower_bound function in more detail.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int arr[] = {1, 3, 5, 7, 9, 11};
int n = sizeof(arr) / sizeof(arr[0]);
int key1 = 6;
int key2 = 15;
auto it1 = lower_bound(arr, arr + n, key1);
auto it2 = lower_bound(arr, arr + n, key2);
if (it1 == arr + n) {
cout<< "The key " << key1 << " is greater than all elements of the array." <<endl;
}
else {
cout<< "The key " << key1 << " is present at position " << (it1 - arr) << " in the array." <<endl;
}
if (it2 == arr + n) {
cout<< "The key " << key2 << " is greater than all elements of the array." <<endl;
}
else {
cout<< "The key " << key2 << " is present at position " << (it2 - arr) << " in the array." <<endl;
}
return 0;
}
Output:
The key 6 is present at position 3 in the array.
The key 15 is greater than all elements of the array.
In the above example, we have an array arr of size n. We want to find the position of the first element in the array that is greater than or equal to two keys: 6 and 15. We use the lower_bound function to find the iterators to the first elements that are greater than or equal to these keys. The iterator it1 points to the element 7 in the array, which is greater than or equal to the key 6. The iterator it2 is equal to arr + n, which means that the key 15 is greater than all elements of the array.
Upper_bound()
In addition to the lower_bound function, the C++ standard library also provides the upper_bound function, which is used to find the first element in a sorted array that is greater than a given value.
Syntax
The syntax for the upper_bound function is similar to the lower_bound function:
std::upper_bound(first, last, value);
In this function, the iterator returned points to the first element in the array that is strictly greater than the given value.
Conclusion
In conclusion, the lower_bound function in C++ is used to find the first element in a sorted array that is greater than or equal to a given value. The function has a time complexity of O(log n) and works only on sorted arrays. The upper_bound function is also available in the C++ standard library, and it is used to find the first element in a sorted array that is strictly greater than a given value.