C++ Algorithm lower_bound function serves as a binary search variant. Its purpose is to provide an iterator that points to the initial element within a sorted range [first, last) that is equal to or greater than the given value val.
The initial iteration utilizes the < operator to compare the elements, while the subsequent version employs the comp function for comparison.
Syntax
default (1) template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
const T& val);
custom (2) template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);
Parameter
A forward iterator referencing the initial element within the range intended for searching.
last: A forward iterator indicating the element immediately following the last element in the range that will be searched.
A custom binary predicate function named comp is defined by the user to compare two arguments and determine if they are in the correct order. This function adheres to the principles of strict weak ordering for arranging elements.
The variable "val" represents a value that serves as the lower limit for comparing elements within the specified range.
Return value
It provides an iterator that points to the initial element within the range that is greater than or equal to the specified value, or the last element if none matches the condition.
Complexity
On average, the complexity scales logarithmically with the distance from the first element to the last element: it conducts a maximum of log base 2 of (N) plus 1 comparisons, where N equals the difference between the last and first elements.
Data races
The elements within the range [first, last) are retrieved.
Exceptions
This function will raise an exception if an error occurs during either comparing elements or performing an operation on an iterator.
Note: The invalid parameters cause an undefined behavior.
Example 1
Let's examine a straightforward example to illustrate the application of lower_bound:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v = {3, 1, 4, 6, 5};
decltype(v)::iterator it = lower_bound(v.begin(), v.end(), 4);
cout << *it << ", pos = " << (it - v.begin()) << endl;
return 0;
}
Output:
4, pos = 2
Example 2
Let's see another simple example:
#include <iostream> // std::cout
#include <algorithm> // std::lower_bound, std::upper_bound, std::sort
#include <vector> // std::vector
using namespace std;
int main () {
int myints[] = {10,20,30,30,20,10,10,20};
vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20
sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30
vector<int>::iterator low,up;
low=lower_bound (v.begin(), v.end(), 20); // ^
up= upper_bound (v.begin(), v.end(), 20); // ^
cout << "lower_bound at position " << (low- v.begin()) << '\n';
cout << "upper_bound at position " << (up - v.begin()) << '\n';
return 0;
}
Output:
lower_bound at position 3
upper_bound at position 6
Example 3
Let's see another simple example:
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
template<class ForwardIt, class T, class Compare=less<>>
ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp={})
{
// Note: BOTH type T and the type after ForwardIt is dereferenced
// must be implicitly convertible to BOTH Type1 and Type2, used in Compare.
// This is stricter than lower_bound requirement (see above)
first = lower_bound(first, last, value, comp);
return first != last && !comp(value, *first) ? first: last;
}
int main()
{
vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };
auto lower = lower_bound(data.begin(), data.end(), 4);
auto upper = upper_bound(data.begin(), data.end(), 4);
copy(lower, upper, ostream_iterator<int>(cout, " "));
cout << '\n';
// classic binary search, returning a value only if it is present
data = { 1, 2, 4, 6, 9, 10 };
auto it = binary_find(data.cbegin(), data.cend(), 4); //< choosing '5' will return end()
if(it != data.cend())
cout << *it << " found at index "<< distance(data.cbegin(), it);
return 0;
}
Output:
4 4 4
4 found at index 2
Example 4
Let's see another simple example:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool ignore_case(char a, char b) {
return(tolower(a) == tolower(b));
}
int main(void) {
vector<char> v = {'A', 'b', 'C', 'd', 'E'};
auto it = lower_bound(v.begin(), v.end(), 'C');
cout << "First element which is greater than \'C\' is " << *it << endl;
it = lower_bound(v.begin(), v.end(), 'C', ignore_case);
cout << "First element which is greater than \'C\' is " << *it << endl;
it = lower_bound(v.begin(), v.end(), 'z', ignore_case);
cout << "All elements are less than \'z\'." << endl;
return 0;
}
Output:
First element which is greater than 'C' is b
First element which is greater than 'C' is d
All elements are less than 'z'.
