191. Unclear complexity for algorithms such as binary search

Section: 28.7.3 [alg.binary.search] Status: NAD Submitter: Nico Josuttis Opened: 1999-10-10 Last modified: 2016-02-10

Priority: Not Prioritized

View all other issues in [alg.binary.search].

View all issues with NAD status.

Discussion:

The complexity of binary_search() is stated as "At most log(last-first) + 2 comparisons", which seems to say that the algorithm has logarithmic complexity. However, this algorithms is defined for forward iterators. And for forward iterators, the need to step element-by-element results into linear complexity. But such a statement is missing in the standard. The same applies to lower_bound(), upper_bound(), and equal_range(). 

However, strictly speaking the standard contains no bug here. So this might considered to be a clarification or improvement.

Rationale:

The complexity is expressed in terms of comparisons, and that complexity can be met even if the number of iterators accessed is linear. Paragraph 1 already says exactly what happens to iterators.