### 191. Unclear complexity for algorithms such as binary search

**Section:** 27.8.4 [alg.binary.search] **Status:** NAD
**Submitter:** Nico Josuttis **Opened:** 1999-10-10 **Last modified:** 2016-01-28 10:19:27 UTC

**Priority: **Not Prioritized

**View all other** issues in [alg.binary.search].

**View all issues with** NAD status.

**Discussion:**

The complexity of binary_search() is stated as "At most
log(last-first) + 2 comparisons", which seems to say that the
algorithm has logarithmic complexity. However, this algorithms is
defined for forward iterators. And for forward iterators, the need to
step element-by-element results into linear complexity. But such a
statement is missing in the standard. The same applies to
lower_bound(), upper_bound(), and equal_range().

However, strictly speaking the standard contains no bug here. So this
might considered to be a clarification or improvement.

**Rationale:**

The complexity is expressed in terms of comparisons, and that
complexity can be met even if the number of iterators accessed is
linear. Paragraph 1 already says exactly what happens to
iterators.