二分探索
ソート済みの列から要素をO(log n)で見つける方法。毎回、探索範囲を半分に絞る。中央を調べて、左か右へ進むだけだ。
情報科学の入門講義で必ず出てくる例題。ところが実装は、よく間違えられることで悪名高い。Knuthは、ほとんどの変種に細かい off-by-one エラーがあると指摘した。JDKのArrays.binarySearchにはオーバーフローのバグが9年間潜んでいた（2006年に発見）。git bisectは、コミット履歴に対する二分探索だ。一般化したものとして、C++ STLのlower_bound/upper_boundが挿入位置を見つける。使えるのはソート済みのデータだけである。