二分探索 (O(log n))

100 万件を、最大20回で探す

線形探索は100万件なら最大100万回比べます。ところが、小さい順に並んだ配列なら、中央を調べて範囲を半分ずつ絞れます。この二分探索では、100万件でも中央の値を調べる回数は最大20回です。

1から100までの数を当てるゲームを考えます。中央の数と比べて、大きければ右側、小さければ左側に絞ります。一致したら終わりです。1から順に全部を尋ねる必要はありません。

中央を調べたら、候補から外す

中央が不一致なら、中央自身も次の候補から外します。15件の配列で毎回大きい側を選ぶ場合、残る候補は次のように減ります。

最後の1件も調べて、不一致なら0件です。4回で探索を終えられます。n件での最大回数は、nが1以上なら floor(log2(n)) + 1 です。log2 は2を何乗するとその数になるか、floor は小数部分の切り捨てを表します。15は8以上16未満なので最大4回です。

件数が倍になるたび最大回数は1増えます。このゆっくりした増え方を O(log n) と書きます。100万は2の19乗以上、20乗未満なので、最大20回です。

並んでいないと、半分を捨てられない

この速さは「中央より大きい値は左側にはない」という判断に支えられています。未整列の配列で半分を捨てると、存在する値を見落とします。昇順に並んでいることが前提です。並べ替えが必要なら、その時間も別にかかります。

両端の位置がleftとrightなら、中央は (left + right) // 2 です。Pythonの // は整数同士の場合、小数部分を切り捨てた整数を返します。

print(7 / 2)   # 3.5
print(7 // 2)  # 3

範囲が縮まないと、終わらない

中央より大きい値を探すなら、左端を中央の次へ進めます。小さいなら右端を中央の手前へ動かします。中央を残すと、同じ場所を何度も調べてしまうことがあります。1件残っているときも、まだ調べる必要があります。

例題で確かめる

在庫番号 [4, 9, 15, 22, 31, 40, 58] から40を探します。両端の位置は0と6なので、中央は3、値は22です。40のほうが大きいため位置4〜6に絞ります。次の中央は位置5、値は40です。2回目で一致しました。線形探索なら先頭から6回必要な場面です。