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

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

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

サンプルコードでは、lowとhighという2つの添字で探索範囲を管理し、真ん中の値midと目標値targetを比較しています。//は「切り捨て除算」というPython独自の演算子で、割り算の結果を整数に切り捨てて計算します。見つからなければ-1を返します。

初心者がよくつまずくのが、対象のデータがあらかじめ並び替えられている必要があるという前提条件です。並び替えられていないリストに対して二分探索を使っても正しい結果は得られません。Pythonにはbisectモジュールという専用の高速な実装も用意されているので、実務ではそちらを使う方法もあります。

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