787. complexity of binary_search

Section: 26.8.4.5 [binary.search] Status: CD1 Submitter: Daniel Krügler Opened: 2007-09-08 Last modified: 2016-01-28

Priority: Not Prioritized

View all issues with CD1 status.

Discussion:

In 26.8.4.5 [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.

Proposed resolution:

Change 26.8.4.5 [binary.search]/3

Complexity: At most log2(last - first) + 2 O(1) comparisons.