Can someone explain why lower_bound is working this way?

Question

lower_bound function of C++ returns a pointer to the first array element that is at least equal to x (the third argument passed to the function). Here is the code which I compiled online using an online compiler for C++.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(1);
    v.push_back(2);
    cout<<lower_bound(v.begin(),v.end(),2)-v.begin()<<endl;
    return 0;
}

Output I expected was 1 but actual result says 3. Can someone please explain why this is so?

From the documentation of [`std::lower_bound`](https://en.cppreference.com/w/cpp/algorithm/lower_bound): "_The range [first, last) must be partitioned with respect to the expression `element < value` or `comp(element, value)`, i.e., all elements for which the expression is `true` must precede all elements for which the expression is `false`. A fully-sorted range meets this criterion._" Your `std::vector` fails this criteria. — Algirdas Preidžius, Jul 10 '20 at 09:44
Unrelated, but please also check out [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — rustyx, Jul 10 '20 at 10:54

score 4 · Answer 1 · answered Jul 10 '20 at 09:43

https://en.cppreference.com/w/cpp/algorithm/lower_bound

The range [first, last) must be partitioned with respect to the expression element < value or comp(element, value), i.e., all elements for which the expression is true must precede all elements for which the expression is false. A fully-sorted range meets this criterion.

This order:

v.push_back(1);
v.push_back(2);
v.push_back(1);
v.push_back(2);

does not fulfill that criterion.

score 4 · Answer 2 · answered Jul 10 '20 at 09:44

4

The range [first, last) must be partitioned with respect to the expression element < value or comp(element, value), i.e., all elements for which the expression is true must precede all elements for which the expression is false. A fully-sorted range meets this criterion.

https://en.cppreference.com/w/cpp/algorithm/lower_bound

Your input does not satisfy this requirement (not sorted), therefore the output is undefined.

answered Jul 10 '20 at 09:44

erenon

18,838
2
61
93

1

The requirement is not that the array be sorted. Using the same call of `lower_bound()` as the OP, a vector with elements `{1, -1, 3, 2}` would correctly give the result expected by the OP. – Peter Jul 10 '20 at 09:53

Zhang · Answer 3 · 2020-07-10T09:57:44.587

std::lower_bound

// lower_bound/upper_bound example
#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort
#include <vector>       // std::vector

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20

  std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

  std::vector<int>::iterator low,up;
  low=std::lower_bound (v.begin(), v.end(), 20); //          ^
  up= std::upper_bound (v.begin(), v.end(), 20); //                   ^

  std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
  std::cout << "upper_bound at position " << (up - v.begin()) << '\n';

  return 0;
}

std::sort (v.begin(), v.end()); is important, the number list has to be in ascend order.

Can someone explain why lower_bound is working this way?

3 Answers3