最初の不良コミットの二分探索

$n \ge 1$ とし、一直線の履歴 $c_0, c_1, \ldots, c_n$ と決定的な検査を考える。検査に不合格のコミットを不良、合格のコミットを良と呼ぶ。$c_0$ は良、$c_n$ は不良と分かっていて、次の単調性が成り立つとする。

ある $f \in \{1, \ldots, n\}$ があって、$c_i$ が不良であることと $i \ge f$ であることが同値である。

この $c_f$ を最初の不良コミットという。

(a) $c_1, \ldots, c_{n-1}$ のうち高々 $\lceil \log_2 n \rceil$ 個を検査すれば、$f$ を特定できる。

(b) 次に検査するコミットをそれまでの検査結果だけから決めるどんな決定的な手順も、ある $f$ に対しては少なくとも $\lceil \log_2 n \rceil$ 回の検査を行う。