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.

### 787. complexity of `binary_search`

Section: 25.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 25.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 25.8.4.5 [binary.search]/3

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