lower_bound() in C++

user_13064645 0
Viewed 695

From reading from the Internet, I understand that The lower_bound() method in C++ is used to return an iterator pointing to the first element in the range [first, last) which has a value not less than value. This means that the function returns the index of the next smallest number just greater than that number.

So, for the given code below I understood that the output is 3. But, as there is repetition of 6. How can I get the index of last 6 using lower_bound(). I can implement my own binary_search() for that, but I want to know how to do it by lower_bound().

#include <iostream> 
#include <algorithm>
#include <vector> 

using namespace std; 

int main () 
{ 
    int array[] = {5,6,7,7,6,5,5,6}; 

    vector<int> 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<int>::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; 
}
binary-search vector algorithm c++
4 Answers

Use pair of lower_bound and upper_bound. Or one equal_range -- that would be more optimal.

Both upper_bound and high part of equal_range would be past the last "6". The same as end is not last, it is past the last.

user_29450270

You can use reverse iterators into the vector, but then to fulfill the ordering requirement for std::lower_bound you need to inverse the comparison, so you need to use std::greater instead of the default std::less. This however also means that now you are not really looking for a lower bound, but for an upper bound with respect to that comparison function, so:

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

If the array is sorted, iterating between lower_bound and upper_bound you get all elements which equal your 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 question you are asking, i.e. what is the index of the last 6, doesn't have a corresponding function in the standard library because is ill-defined in the case when the range doesn't contain any 6. In all other cases since you have a random access container you can get an iterator to the last 6 by removing one from upper_bound (upper - 1 in your code), in the same way you get the last index of an array by removing 1 from length. However I suggest you avoid relying on the position of the last element equal when you design your algorithm. Also note that if you need both lower and upper bound you can get both at the same time with equal_range, which may even perform better because it may be optimised to only traverse the data structure once:

std::tie(lower,upper) = equal_range(v.begin(), v.end(), 6);

for (auto it = lower; it != upper; it++) {
    assert(6 == *it);
}
user_6861840

You can use lower_bound again, updating the begin and the 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';
user_49444250
Related