二分探索シミュレーター

ALGORITHM

二分探索とは何をしているか

二分探索（バイナリサーチ）は、小さい順に並んだ配列に対して、真ん中の要素と探したい値 target を比べ、 大小の関係から目的の値が存在しない側を丸ごと捨てる探索です。 辞書で単語を引くとき、真ん中あたりを開いて「もっと後ろだ」と判断して前half を見なくなるのと同じ考え方です。

使う変数は3つです。範囲の下端 low、範囲の上端 high、そしてその中央 mid。 シミュレーターではこの3つがマスの上に L・M・H として表示され、候補から外れたマスは薄い破線になります。 「次へ」を押すたびに、薄いマスが一気に増えていく様子が確認できます。

1回の比較で候補が半分になる

線形探索は1回の比較で候補が1個しか減りませんが、二分探索は半分減ります。 この差は要素数が増えるほど大きくなります。

100万個の中から探すのにたった20回で済みます。これが二分探索の強さで、 「整列してから探す」という手順に意味がある理由です。

mid の小数は切り捨てる

mid = (low + high) ÷ 2 で計算しますが、添字は整数でなければ配列を指せません。 そのため小数点以下は切り捨てます。たとえば low = 0、high = 5 なら (0 + 5) ÷ 2 = 2.5 なので mid = 2 です。 シミュレーターでは、割り切れないときに「÷ は小数を切り捨てます」と表示されるので、実際の値と合わせて確認してください。

整列されていないと失敗する

二分探索が成り立つのは、「中央より大きいなら、目的の値は右側にしかない」と言い切れるからです。 並びが崩れていると、この判断が成り立ちません。捨てた側に目的の値が残っていても、二度と調べられないため見つけられません。

CODE

3つの書き方で見る二分探索

擬似言語（DNCL風）・Python・JavaScript で並べました。変数名と処理の順番はすべて揃えてあります。

Nums = [2, 5, 8, 11, 14, 20]
target = 14
low = 0
high = 要素数(Nums) - 1
pos = -1

low <= high の間繰り返す:
｜mid = (low + high) ÷ 2
｜もし Nums[mid] == target ならば:
｜｜pos = mid
｜｜繰り返しを抜ける
｜そうでなくもし Nums[mid] < target ならば:
｜｜low = mid + 1
｜そうでなければ:
⎿⎿ high = mid - 1

表示する(pos)

nums = [2, 5, 8, 11, 14, 20]
target = 14
low = 0
high = len(nums) - 1
pos = -1

while low <= high:
    mid = (low + high) // 2
    if nums[mid] == target:
        pos = mid
        break
    elif nums[mid] < target:
        low = mid + 1
    else:
        high = mid - 1

print(pos)

const nums = [2, 5, 8, 11, 14, 20];
const target = 14;
let low = 0;
let high = nums.length - 1;
let pos = -1;

while (low <= high) {
  const mid = Math.floor((low + high) / 2);
  if (nums[mid] === target) {
    pos = mid;
    break;
  } else if (nums[mid] < target) {
    low = mid + 1;
  } else {
    high = mid - 1;
  }
}

console.log(pos);

COST

比較回数と計算量

要素数を n とすると、候補は n → n/2 → n/4 → … と減り、1個になるまでの回数は約 log2(n) 回です。 シミュレーターで「中央」と「左端」を切り替えると、同じ配列でも比較回数が変わることが確認できます。

要素数が2倍になっても、比較回数は1回だけ増えます。線形探索が2倍になるのとは大きな違いです。 ただし、整列されていない配列を先に並べ替える場合は、その整列自体に手間（交換法や選択法なら n² に比例）がかかります。 1回だけ探すなら線形探索、何度も探すなら整列してから二分探索、という使い分けが問われることがあります。

EXAM POINT

共通テスト「情報Ⅰ」での出題ポイント

二分探索は、穴埋めとトレース（値の追跡）の両方でよく出ます。狙われやすいのは次の5点です。

1. mid の式：mid = (low + high) ÷ 2 の空欄。切り捨てになることも合わせて確認されます。
2. 範囲の更新：low = mid + 1 と high = mid - 1 のどちらを使うか。「大きければ低い側を捨てる」の向きを間違えないことが要点です。
3. 繰り返しの条件：low <= high の <= 部分。< にすると、候補が1個になった場面を調べ落とします。
4. 前提条件：「このアルゴリズムを使うために配列が満たすべき条件は何か」という問い。答えは「小さい順（または大きい順）に整列していること」です。
5. 比較回数：「最大で何回の比較が必要か」。要素数 8 なら 4 回、16 なら 5 回のように、半分にしていく回数を数えます。

MISTAKES

よくある間違い

CHECK

理解度チェック

まず自分で考え、答えを開く前に上のシミュレーターで確かめてみてください。