二分探索
整列済みの配列で値を探します。真ん中を見て、値がありえない半分を捨てます。比較のたびに残りが半分になります。
- 最良 Ω(1)
- 平均 Θ(log n)
- 最悪 O(log n)
- メモリ O(1)
用語の意味
- 整列済み:昇順に並んでいること。二分探索にはこれが必要で、整列していないデータでは誤った答えを返します。
- 半分にする:比較のたびに、目標がありえない側の半分を捨てること。
- log₂ n:1 になるまで n を何回半分にできるか。64個なら6回なので、比較は最大7回です。
- 真ん中 (mid)
- 発見
- 除外
- 目標
探索が選びうるすべての真ん中。1回の実行は下へ向かう1本の道です。段数: 5 = ⌈log₂(24 + 1)⌉、必要になりうる最大の比較回数です。
24個の整列済みの値から 70 を探します。まだ配列全体が候補です。
スペースキー: 再生・一時停止。左右の矢印キー: ステップ移動。Home キーと End キー: ジャンプ。
試してみましょう: 配列にない目標を選んでください。それでも探索は、lo が hi を追い越した時点で、最大 ⌈log₂(n + 1)⌉ 回の比較で終わります。
仕組み
二分探索は、目標がまだありうる範囲の両端に lo と hi という2つの印を置きます。真ん中の値を見て、それが目標なら終わり。小さければ目標は右側にしかないので lo を真ん中の先へ、大きければ hi を真ん中の手前へ動かします。1歩ごとに残りが半分になるので、64個なら最大7回、100万個でも最大20回の比較で済みます。lo が hi を追い越したら何も残っていません。値は配列にありません。
向いている場面
データが整列済みで、どの位置にもすぐ移動できるなら二分探索を使います。整列済みリストの単語、リリース履歴のバージョン、git bisect、整列済み配列への挿入位置などです。整列していないデータでは誤った答えを返します。先に整列するのは、何度も探す場合にだけ割に合います。