Section: 126.96.36.199 [binary.search] Status: CD1 Submitter: Daniel Krügler Opened: 2007-09-08 Last modified: 2016-02-10
Priority: Not Prioritized
View all issues with CD1 status.
In 188.8.131.52 [binary.search] p. 3 the complexity of binary_search is described as
At most log(last - first) + 2 comparisons.
This should be precised and brought in line with the nomenclature used for lower_bound, upper_bound, and equal_range.
All existing libraries I'm aware of, delegate to lower_bound (+ one further comparison). Since issue 384 has now WP status, the resolution of #787 should be brought in-line with 384 by changing the + 2 to + O(1).
[ Sophia Antipolis: ]
Alisdair prefers to apply an upper bound instead of O(1), but that would require fixing for lower_bound, upper_bound etc. as well. If he really cares about it, he'll send an issue to Howard.
Change 184.108.40.206 [binary.search]/3
Complexity: At most log(last - first) +