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

合格発表の問題

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

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

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

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

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

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

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

方法 3 :二分探索法を使う

この記事は
Members+会員の方のみ御覧いただけます

ログイン/無料会員登録

会員サービスの詳細はこちら