Time complexity of std::lower_bound on a sorted vector

Question

I was studying std::upper_bound from http://www.cplusplus.com/reference/algorithm/upper_bound/ 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.

Convalesce

std::vector<T>::iterator is of a random access category – Hufnagel

So it will run in logarithmic time then? – Convalesce

Yes, it will run with lg_n complexity – Hufnagel

thanks now I will now get to learning random - access iterators. – Convalesce

Note that "sorted" is a requirement of the algorithm, not an option that changes its performance characteristics. If the vector is not sorted, the behavior of the algorithm is undefined. – Goddard

Examples of non-random access iterators are std::list::iterator, std::set::iterator – Feminine

Answer 1

§ 23.3.6.1 [vector.overview]/p1:

A vector is a sequence container that supports random access iterators.

A random access iterator is the one that is able to compute the offset of an arbitrary element in a constant time, without a need to iterate from one place to another (what would result in linear complexity).

std::lower_bound itself provides generic implementation of the binary search algorithm, that doesn't care much about what iterator is used to indicate ranges (it only requires the iterator to be of at least a forward category). It uses helper functions like std::advance to iteratively limit the ranges in its binary search. With std::vector<T>::iterator which is of a random access category, std::lower_bound runs with logarithmic time complexity with regards to the number of steps required to iterate over elements, as it can partition the range by half in each step in a constant time.

§ 25.4.3 [alg.binary.search]/p1:

All of the algorithms in this section are versions of binary search and assume that the sequence being searched is partitioned with respect to an expression formed by binding the search key to an argument of the implied or explicit comparison function. They work on non-random access iterators minimizing the number of comparisons, which will be logarithmic for all types of iterators. They are especially appropriate for random access iterators, because these algorithms do a logarithmic number of steps through the data structure. For non-random access iterators they execute a linear number of steps.

Hufnagel