CODEWITHSUNDEEP
c++algorithmvector
sarcasvik
sarcasvik

Reputation: 35

lower_bound function is returning the wrong iterator

In the following code both 7 and 4 are returning the same value i.e. 2 meanwhile every else number is returning the right index

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
    vector<int> v;

    v.push_back(1);
    v.push_back(3);
    v.push_back(7);
    v.push_back(4);
    v.push_back(9);
    cout<<"lower bound : "<<lower_bound(v.begin(),v.end(),7)-v.begin()<<endl;
    cout<<"lower bound : "<<lower_bound(v.begin(),v.end(),4)-v.begin()<<endl;
}

output:

lower bound : 2
lower bound : 2

I don't understand what's wrong with the code.

Upvotes: 0

Views: 143

Answers (2)

songyuanyao
songyuanyao

Reputation: 172894

The vector should be sorted in advance. E.g.

std::sort(v.begin(), v.end());
cout<<"lower bound : "<<lower_bound(v.begin(),v.end(),7)-v.begin()<<endl; // ->3
cout<<"lower bound : "<<lower_bound(v.begin(),v.end(),4)-v.begin()<<endl; // ->2

Upvotes: 3

HolyBlackCat
HolyBlackCat

Reputation: 96081

lower_bound finds the first element that's greater-or-equal than the third parameter.

So lower_bound(v.begin(),v.end(),4) corretly finds 7.

On the other hand, lower_bound(v.begin(),v.end(),4) causes undefined behavior since your vector violates the precondition:

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.

Upvotes: 0

Related Questions