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

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

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

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

初心者がよくつまずくのが、対象のデータがあらかじめ並び替えられている必要があるという前提条件です。並び替えられていない配列に対して二分探索を使っても正しい結果は得られません。またlowとhighの更新を間違えると、無限ループに陥ってしまう点にも注意が必要です。

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