Section: 26.8.4 [alg.binary.search] Status: NAD Submitter: Nico Josuttis Opened: 1999-10-10 Last modified: 2016-01-28
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.