STAGE 2
二分探索
半分に切って log N 回
🎯 ミッション
二分探索のしくみと、比べる回数が log₂ N になる理由を説明できるようになろう。1000人の名簿で10回以内に目的の人を見つけ、確認クイズに全問正解すれば合格。
未達成

ねこ博士
村長の名簿は、実は五十音順に並んでいる。辞書で言葉を引くとき、きみは1ページ目から順にめくる?

うさ美
めくらないです。だいたい真ん中あたりを開いて、探している言葉より前なら前のほう、後なら後ろのほうを開き直します。

ねこ博士
それをきっちり手順にしたのが二分探索だ。並んでいる名簿の真ん中の人と比べる。探している人が真ん中より前なら、後ろ半分にはいないので、後ろ半分は丸ごと捨てていい。後ろなら前半分を捨てる。残った範囲で、また真ん中と比べる。

うさ美
1回比べるごとに、調べる範囲が半分になる。1000人なら、500、250、125、63、32、16、8、4、2、1……10回で1人に絞れます。

ねこ博士
では、N 人のとき何回で1人に絞れるか。「N を2で何回割れば1になるか」だね。この回数を、2を底とする N の対数と呼び、log₂ N(ログ 2 の N)と書く。2 を何回掛けると N になるか、と言っても同じだ。
log₂ N = 2 を何回掛けると N になるか(= N を2で何回割ると1になるか)
log₂ 8 = 3(2×2×2=8) / log₂ 1024 = 10 / log₂ 約100万 = 約20 / log₂ 約10億 = 約30
二分探索の比べる回数(最悪):約 log₂ N 回 → 計算量 O(log N)

うさ美
100万人でも20回、10億人でも30回。人数が1000倍になっても、10回増えるだけなんですね。線形探索なら1000倍になるのに。

ねこ博士
そう。O(log N) は、O(N) とは比べものにならないほど増え方が小さい。ここで、二分探索が使える条件をはっきりさせておこう。何が必要だったかな。

うさ美
名簿が並んでいること。並んでいないと、真ん中と比べても、どちらの半分にいるか分からない。

ねこ博士
もう1つある。「真ん中の人」にすぐ行けること。紙の名簿や、番地が連続した配列なら、ページ番号や番地の計算1回で真ん中に行ける。でも、鎖のようにつながった連結リストだと、真ん中に行くには前から半分たどる必要があるので、二分探索の良さが消えてしまう。
二分探索の条件:① データが並んでいる ② 何番目にでもすぐ行ける(配列など)

うさ美
でも、名簿に新しい人が増えたら、並びを保つために、正しい位置に入れないといけないですよね。その手間は?

ねこ博士
いいところに気づいたね。配列だと、途中に1人入れるには後ろを全部1つずつずらすので、O(N) かかる。探すのは速いけれど、増やすのは遅い。探すのも増やすのも速くしたい、という欲張りな願いに応える方法が、次のステージのハッシュ表だ。それから、そもそも「並べる」こと自体にも手間がかかる。それは STAGE4 と STAGE5 で考えよう。
確認クイズ
Q1. 二分探索で、1回比べるごとに起きることは?
正解! 真ん中と比べれば、探している人がいない側の半分を丸ごと捨てられる。
Q2. 約100万人の並んだ名簿で、二分探索なら最悪およそ何回比べれば見つかる?
正解! 2を20回掛けると約100万(1,048,576)。だから約20回で1人に絞れる。
Q3. 二分探索が使えないのは、どんな場合?
正解! 並んでいなければ、真ん中と比べても、どちらの半分にいるか決められない。いない場合も、範囲が空になったところで「いない」と分かる。