Proposed resolution:

Change [binary.search]/3

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

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

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