Sportsman's blog

Regarding lower_bound in c++
By Sportsman, history, 4 years ago, In English

We all know that we can also use sort function for a specific portion of a vector. Eg: let a vector be v = {24, 11, 5, 7, 6} , now if we want to sort only last three elements, we can write sort(v.begin()+2,v.end()) Likewise, I thought we can also use lower_bound(v.begin()+2,v.end(),6) to find the lower_bound for 6 in the last three elements. But that's not working. May i please know where I'm going wrong . It seems the lower_bound and upper_bound functions only work for the whole vector despite our attempts & wants. Please correct me if I'm wrong.

  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

How is it "not working"? Show some code, expected output and actual output.

For what it's worth, lower_bound and upper_bound don't care whether or not they are getting the full range. So it's almost certainly an error in your usage.

→ Reply
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

{5, 7, 6} is not sorted.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it -35 Vote: I do not like it

    Yah,i did it intentionally. But now i realise that i didn't understand lower_bound at all, i thought when the vector is not sorted, the output would be the first element which is greater or equal to the passed value.

    int main(){     
    vector<int> v{24,11,5,7,6};
    auto it = lower_bound(v.begin(),v.end(),6);
    cout<<*it;
}

    I expected the output for this will be 24. But the output is 7. Can you help me with this.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +41 Vote: I do not like it

      lower_bound is binary search, so you get garbage output if vector is not sorted.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -22 Vote: I do not like it

        oh my god...i didn't know that lower_bound is binary search, thank you so much! All my doubts are now clarified :)

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +24 Vote: I do not like it

          Just curious: how did you assume lower_bound worked? That too in O(logn) time?

          → Reply