Issue 787: complexity of binary_search (original) (raw)

This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of CD1 status.

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 forlower_bound, upper_bound, and equal_range.

All existing libraries I'm aware of, delegate tolower_bound (+ one further comparison). Since issue 384(i) has now WP status, the resolution of #787 should be brought in-line with 384(i) by changing the + 2to + 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.