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
Vectors have random access iterators, so you can use upper_bound() and lower_bound() with logarithmic time complixities.
A set has non-random iterators, because auf this you should not use
Because this above does not work good, set has its own version of lower_bound which works in $$$O(logn)$$$