Lower_bound() in C++

It’s worth noting that if you require both the lower and upper bounds, you can obtain them simultaneously using the same method. This approach may even be more efficient because it could be optimized to traverse the data structure only once. Another alternative is Solution 4, which uses the same method as before but modifies the begin and value parameters. Based on my online research, I learned that the method in C++ returns an iterator that points to the first element in the [first, last) range with a value greater than or equal to the specified value.

Question:

After researching online, my understanding is that in C++, the

lower_bound()

method returns an iterator that points to the first element within the range [first, last) that has a value greater than or equal to the specified value. Essentially, this function identifies the index of the smallest number that is greater than the given number.

After analyzing the code given below, I concluded that the output is 3. However, since there is a recurrence of 6, I am uncertain about how to obtain the index of the last occurrence using

lower_bound()

. While I could create my own solution using

binary_search()

, I am interested in learning how to accomplish this using

lower_bound()

.

#include  
#include 
#include  
using namespace std; 
int main () 
{ 
    int array[] = {5,6,7,7,6,5,5,6}; 
    vector v(array,array+8); // 5 6 7 7 6 5 5 6 
    sort (v.begin(), v.end()); // 5 5 5 6 6 6 7 7 
    vector::iterator lower,upper; 
    lower = lower_bound (v.begin(), v.end(), 6); 
    upper = upper_bound (v.begin(), v.end(), 6); 
    cout << "lower_bound for 6 at position " << (lower- v.begin()) << 'n'; 
    return 0; 
} 




Solution 1:

Utilize a combination of

lower_bound

and

upper_bound

, or alternatively, opt for a single

equal_range

for the most efficient solution.

The

upper_bound

and

equal_range

high part would both be located beyond the last “6”. Similarly, while the end is not the last, it is still located beyond the last.


Solution 2:


To comply with the ordering requirement for

std::lower_bound

, you may utilize reverse iterators of the vector. However, to achieve this, you will need to invert the comparison, substituting the default

std::less

with

std::greater

. It is important to note that this approach changes the search from a lower bound to an upper bound based on the new comparison function.

auto upper = std::upper_bound(v.rbegin(), v.rend(), 6, std::greater{});


Solution 3:


When the array is arranged in a particular order, by traversing from

lower_bound

to

upper_bound

, you are able to obtain all the elements that match the pivot point.

lower = lower_bound(v.begin(), v.end(), 6);
upper = upper_bound(v.begin(), v.end(), 6);
for (auto it = lower; it != upper; it++) {
    assert(6 == *it);
}

The inquiry you’re making, which is the index of the last occurrence of

6

, lacks a corresponding function in
standard library
because it’s unclear when the range doesn’t possess any

6

. However, in all other cases, you can obtain an iterator to the last

6

by subtracting one from

upper_bound

(i.e.,

upper - 1

in your code) as you can get the last index of an array by subtracting one from its length. Nonetheless, I advise you not to depend on the position of the last element when designing your algorithm. Besides, note that you can obtain both lower and upper bounds simultaneously with

equal_range

, which might be more efficient because it could optimize the data structure’s traversal.

std::tie(lower,upper) = equal_range(v.begin(), v.end(), 6);
for (auto it = lower; it != upper; it++) {
    assert(6 == *it);
}


Solution 4:

Utilize

lower_bound

once more by modifying its starting point and numerical value.

auto lower = std::lower_bound (v.cbegin(), v.cend(), 6); 
auto upper = std::lower_bound (lower, v.cend(), 6 + 1);
std::cout << "Number of values found: " << std::distance(lower, upper) << 'n'; 

Frequently Asked Questions

Posted in Uncategorized