**Section:** 27.8.4.5 [binary.search] **Status:** CD1
**Submitter:** Daniel Krügler **Opened:** 2007-09-08 **Last modified:** 2016-01-28 10:19:27 UTC

**Priority: **Not Prioritized

**View all issues with** CD1 status.

**Discussion:**

In 27.8.4.5 [binary.search] p. 3 the complexity of `binary_search` is described as

At most

log(last - first) + 2comparisons.

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_boundetc. as well. If he really cares about it, he'll send an issue to Howard.

**Proposed resolution:**

Change 27.8.4.5 [binary.search]/3

Complexity:At mostlogcomparisons._{2}(last - first) +~~2~~O(1)