- 目標値
- 残りの候補
- 比較中
- 除外
- 発見
二分探索
二分探索は、常に中央を見ることで整列済みリストから値を探します。中央の値が小さすぎれば目標はその後ろにしかなく、大きすぎればその前にしかありません。どちらにしても残りの半分が除外されます。探す値を選んで探索を1ステップずつ進め、目標が見つかるか何も残らなくなるまで網掛けの部分が縮んでいく様子を見てください。 「再生」で探索を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。破線は探す値を示し、網掛けの部分はその値がまだありうる範囲です。二分探索には整列済みのリストが必要なので、整列されていないリストは先に並べ替えます。探す値や棒の数を選ぶか、数値を自分で入力できます。ボードを選択中は、矢印キーで1ステップ移動、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- 探す値と棒の数を選びます。数値を自分で入力することもできます。二分探索はまずそれを並べ替えます。
- 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると、探索の好きな位置に移動できます。
- 末尾に近い値やリストにない値で、「比較」タイルと「線形探索なら」を比べてみましょう。
二分探索のしくみ
整列済みリストのうち、まだ目標がありうる部分を覚えておきます。最初はリスト全体です。その中央の値を見ます。目標と等しければ終わりです。小さければ目標はその後ろにしかないので、中央より後ろの部分で続けます。大きければ前の部分で続けます。何も残らなくなったら、目標はリストにありません。
なぜこんなに速いのか
比較のたびに残りの部分が半分になります。n個の値から始めると、k回の比較の後に残るのは最大でおよそ n/2ᵏ 個なので、探索は最大 ⌊log₂ n⌋ + 1 回の比較で終わります。40個なら6回、1,000個なら10回、100万個なら20回です。線形探索ではすべての値を見る必要があるかもしれません。ただし、リストは整列済みでなければならず、整列を保つことや先に並べ替えることにもコストがかかります。
よくある質問
二分探索はどのように動きますか?
整列済みリストのうち、まだ目標がありうる部分の中央の値と目標を比較します。等しければ見つかりです。そうでなければ目標がありえない半分を捨て、目標が見つかるか何も残らなくなるまで、もう半分で探索を続けます。
二分探索には何回の比較が必要ですか?
n個の値のリストなら最大 ⌊log₂ n⌋ + 1 回です。40個なら6回、1,000個なら10回、100万個なら20回。比較のたびに残りが半分になります。
なぜ二分探索には整列済みのリストが必要なのですか?
整列済みのリストでなければ、1回の比較で目標がどちら側にあるかわからないからです。整列されていないリストでは、中央の値が小さくても目標の位置について何もわからず、何も除外できません。
重複があるとき、どの値が見つかりますか?
中央がどこに来るかによって、そのうちのどれか1つです。一致した後も左または右へ探索を続ける変種なら、最初または最後の出現位置が見つかります。
入力した数値はどこかに送信されますか?
いいえ。探索はブラウザ内で実行され、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ