二分探索(バイナリサーチ)のアルゴリズム

このレッスンでは、二分探索というアルゴリズムを学び、並び替え済みのデータから効率よく目的の値を見つける方法を理解することを目標にします。「Ruby 二分探索 実装」で調べている方向けの内容です。

二分探索は、並び替え済みのデータから目的の値を効率よく探すアルゴリズムです。「辞書を開くとき、真ん中あたりから探して範囲を半分に絞っていく」ようなイメージです。先頭から1つずつ調べる方法に比べて、データ量が多いほど圧倒的に速く目的の値を見つけられます。

サンプルコードでは、lowとhighという2つの添字で探索範囲を管理し、真ん中の値midと目標値targetを比較しています。目標値の方が大きければ範囲の下半分を、小さければ上半分を切り捨てることで、調べる範囲が半分になっていく仕組みです。

初心者がよくつまずくのが、対象のデータがあらかじめ並び替えられている必要があるという前提条件です。並び替えられていない配列に対して二分探索を使っても正しい結果は得られません。事前のソートを忘れないようにしましょう。

データ構造とアルゴリズムの基礎として、就職試験のコーディングテストなどでもよく出題される定番の題材です。データ量が多いシステムでは、二分探索の高速さが特に大きな効果を発揮します。