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