Movatterモバイル変換

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

787. complexity ofbinary_search

Section: 26.8.4.5[binary.search]Status:CD1Submitter: Daniel KrüglerOpened: 2007-09-08Last modified: 2016-01-28

Priority:Not Prioritized

View all issues withCD1 status.

Discussion:

In 26.8.4.5[binary.search] p. 3 the complexity ofbinary_search is described as

At mostlog(last - first) + 2 comparisons.

This should be precised and brought in line with the nomenclature used forlower_bound,upper_bound, andequal_range.

All existing libraries I'm aware of, delegate tolower_bound (+ one further comparison). Sinceissue384⁽ⁱ⁾ has now WP status, the resolution of #787 shouldbe brought in-line with384⁽ⁱ⁾ by changing the+ 2to+ O(1).

[Sophia Antipolis:]

Alisdair prefers to apply an upper bound instead of O(1), but that wouldrequire fixing forlower_bound,upper_bound etc. as well. If he reallycares about it, he'll send an issue to Howard.

Proposed resolution:

Change 26.8.4.5[binary.search]/3

Complexity: At mostlog2(last - first) +2O(1) comparisons.