srijith1402's blog

Clarification regarding upper_bound() and lower_bound().
By srijith1402, history, 4 years ago, In English

I was studying std::upper_bound from documentation of c++ and I came across the fact that this might run in linear time on non-random access iterators.

I need to use this for a sorted vector. Now I don't know what are non-random access iterators and whether this will run in logarithmic time on the sorted vector.

Can anyone clear this for me that how to implement lower_bound() on a sorted vector in log(n) time. Thank you

  • Vote: I like it
  • +3
  • Vote: I do not like it

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

Vectors have random access iterators, so you can use upper_bound() and lower_bound() with logarithmic time complixities.

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

A set has non-random iterators, because auf this you should not use

set<int> myset;
...
auto it=lower_bound(myset.begin(), myset.end(), someval);

Because this above does not work good, set has its own version of lower_bound which works in $$$O(logn)$$$

set<int> myset;
...
auto it=myset.lower_bound(someval);
→ Reply