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.
191. Unclear complexity for algorithms such as binary searchSection: 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.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4