半分にすると、なぜ20回で済むのか

「二分探索にはソート済みの配列が要る」と教わることが多いはずです。ところが C++ 標準ライブラリの規定はそれより弱い条件です。cppreference の std::lower_bound(2026-09-18 取得)より。

Searches for the first element in the partitioned source range [first, last) which is not ordered before value.

要求は partitioned(分割済み)、つまり「探している述語について前半が false・後半が true に分かれている」ことです。ソート済みはこれを満たす一例であって、必要条件ではありません。満たさなかった場合の規定が続きます。

If the elements e of the source range are not partitioned with respect to the expression bool(e < value) (until C++20) bool(std::less{}(e, value)) (since C++20), the behavior is undefined.

「見つかりませんでした」が返るのではありません。何が返るか決まっていません。

では、なぜ実用上はソート済みを使うのか。同じページの Notes が理由を書いています。

Although std::lower_bound only requires the source range to be partitioned, this algorithm is usually used in the case where the source range is sorted, so that the binary search is valid for any value.

特定の1つの値についてだけなら partitioned で足りますが、任意の値について正しくあるには結局ソート済みが要る——この関係です。

計算量の規定も言葉が選ばれています。

Given N as std::distance(first, last): 1) At most log₂(N)+𝓞(1) comparisons with value

comparisons(比較)の回数です。同じページの Notes にこうあります。

If ForwardIt is not a LegacyRandomAccessIterator, the number of iterator increments is linear in std::distance(first, last).

連結リストのように「何番目」へ一発で飛べない列では、真ん中へ移動する手間が線形に掛かります。比較が20回でも、そこへたどり着くのに100万歩あるくなら意味がありません。

git bisect の公式ドキュメント(2026-09-18 取得)の説明です。

This command uses a binary search algorithm to find which commit in your project's history introduced a bug. You use it by first telling it a "bad" commit that is known to contain the bug, and a "good" commit that is known to be before the bug was introduced. Then git bisect picks a commit between those two endpoints and asks you whether the selected commit is "good" or "bad". It continues narrowing down the range until it finds the exact commit that introduced the change.

narrowing down the range ——範囲を絞る、と公式が書いています。そしてバグ探しに限らないことまで明言されています。

In fact, git bisect can be used to find the commit that changed any property of your project; e.g., the commit that fixed a bug, or the commit that caused a benchmark's performance to improve. To support this more general usage, the terms "old" and "new" can be used in place of "good" and "bad", or you can choose your own terms.

「バグが入ったコミット」ではなく「任意の性質が変わったコミット」。判定できる性質なら何でもよい、というのが公式の立場です。実行例の出力はこうなっています。

Bisecting: 675 revisions left to test after this (roughly 10 steps)
 
(good / bad を1回答えた後)
 
Bisecting: 337 revisions left to test after this (roughly 9 steps)

残りが 675 から 337 へ概ね半分になり、steps が10から9へ1減っています。

ここで線を引いておきます。公式ドキュメントに「log₂ 回で見つかる」という式は書かれていません。 書かれているのは上の出力だけです。検算は教材側でできます。log₂(675) = 9.40 なので、切り上げて ceil(log₂(675)) = 10。出力の roughly 10 steps と一致します。数字は合いますが、「公式がそう書いている」と言ってはいけない部分です。

同じ形はコミット履歴以外にも現れます。怪しい範囲の半分をコメントアウトする、設定ファイルの半分を無効にする——どれも「境目を挟み撃ちにする」同じ手順です。Angular コースのデバッグ回でも、この型を扱っています。