This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of NAD status.
Section: 23.7.3 [alg.binary.search] Status: NAD Submitter: Nico Josuttis Opened: 1999-10-10 Last modified: 2016-12-23
Priority: Not Prioritized
View all other issues in [alg.binary.search].
View all issues with NAD status.
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.
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.