lower_bound() giving unexpected result

Question

I wrote a code where I need to find lower_bound from square number sequence. But lower bound giving me result for upper_bound.

Here is my code & compiler link: http://cpp.sh/3cppb

// Example program
#include <iostream>
#include <string>
#include <algorithm>

int main()
{
   std::vector<int> v{ 1, 4, 9, 16, 25 }; // all the square numbers
   
   int x = std::lower_bound(v.begin(), v.end(), 5) - v.begin() ;
   
   std:: cout<<"Postion "<<x<< "  value  "<<v[x] <<std::endl; //getting output for upperbound
   
}

Output:

Postion 2  value  9

Expected Output

Postion 1  value  4

Why do you expect `std::lower_bound` to return iterator to 4, not 9? — Slava, Oct 02 '18 at 18:41
https://stackoverflow.com/questions/51954487/upper-lower-bounds-dont-work-as-i-expect-can-not-understand-why/51954970#51954970 — Slava, Oct 02 '18 at 18:54
@Slava Nice explanation there.. I won't forget it. Thanks a lot. <3 — Sayed Sohan, Oct 02 '18 at 19:00

Edgar Rokjān · Accepted Answer · 2018-10-02T18:49:33.807

3

std::lower_bound returns the iterator to the first element which is greater or equal to the target value:

Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found.

As 9 is the first value which is greater or equal to 5 (it is greater, of course), the result is totally correct.

If you tried to find an element which is already in v, like 9, then you would get different results for std::lower_bound and std::upper_bound:

std::distance(begin(v), std::lower_bound(begin(v), end(v), 9)); // 2
std::distance(begin(v), std::upper_bound(begin(v), end(v), 9)); // 3

edited Oct 02 '18 at 18:49

answered Oct 02 '18 at 18:37

Edgar Rokjān

17,245
4
40
67

Thanks for the clarifications :) . I thought Something is wrong as getting same answers for both lower_bound and upper_bound – Sayed Sohan Oct 02 '18 at 18:41
@SyedSohan when element is not in the range, result of `lower_bound` is equal to `upper_bound`, this is what `std::equal_range` returns – Slava Oct 02 '18 at 18:42
You need to submit `begin(v)` as the first argument to `std::distance` not second. – Slava Oct 02 '18 at 18:48
@Slava yup, or set -2 and -3 :) – Edgar Rokjān Oct 02 '18 at 18:49

score 1 · Answer 2 · answered Oct 02 '18 at 18:42

std::lower_bound is working correctly. The function returns the first element that is not less than the value provided. Since 9 is the first value that is not less than 5 you get that element.

std::upper_bound in this case will return the same element as it returns the first element greater than the specified value. Where you will see a difference is cases like

std::vector data = {4,4,4};
auto low = std::lower_bound(data.begin(), data.end(), 4);
auto high = std::upper_bound(data.begin(), data.end(), 4);

In this case low will be begin() as 4 is not less than 4 while high will be end() as there is no element greater than 4 in the vector.

score 1 · Answer 3 · answered Oct 02 '18 at 18:42

The quotation from the Standard, [lower.bound]:

template<class ForwardIterator, class T> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

Returns: The furthermost iterator i in the range [first,last] such that for every iterator j in the range [first,i) the following corresponding conditions hold: *j < value.

lower_bound() giving unexpected result

3 Answers3