二分探索法とは？

二分探索法は、値の検索を効率的に行うアルゴリズムの一つです。いくつかの要素の中に「ある要素」が存在するかどうかを判定する際、一つずつ調べていくのが最も自然な方法ですが、それでは時間がかかってしまいます。そこで、候補の数を半分に減らし続けることで、効率的に検索を行おうという考え方が二分探索法です。今回は、受験の合格発表を例にして、このアルゴリズムを解説します。

合格発表の問題

次の掲示板には合格者 63 名の受験番号が記されています。そこに、自分の受験番号（仮に、2525 番とする）が存在するかどうかを調べてみましょう。どのようにすれば効率的に見つけられるでしょうか。

方法 1 ：一つずつ探していく

まず、「1008 番は自分の受験番号か？」「1025 番は自分の受験番号か？」「1066 番は自分の受験番号か？」といったように、前から順番に一つずつ調べる方法が考えられます。しかしこの方法を使うと、最大 63 回の比較を行う必要があり、非効率的です。実際の合格発表では人数がさらに多い場合もあり、時間がかかってしまいます。

方法 2 ：まず何列目かを調べる

そこで、自分の受験番号が何列目にあるかを調べてから、その列に絞って番号を探す方法が考えられます。例えば受験番号 2525 を探す手順は次のようになります。

• 手順 1 ：一番上の行を確認し、自分の番号が何列目にあるかを調べる
• 手順 2 ：自分の受験番号は 2377 以上 2601 未満なので、 7 列目にあることが分かる
• 手順 3 ：7 列目のどこに自分の番号があるかを一つずつ確認する

この場合、合計 16 回（手順 1 と 3 それぞれ 8 回ずつ）の比較をする必要があります。方法 1 よりは効率的になりましたが、さらに効率良く自分の番号を探す方法はないでしょうか。