二分探索 | Programming Place Plus　用語集

名称

• 二分探索　【binary search】
• バイナリサーチ　【binary search】
• (表記ゆれ) ２分探索　【binary search】
• (表記ゆれ) バイナリーサーチ　【binary search】

解説

探索アルゴリズムの一種で、データ列がソートされていることを利用して、探索対象範囲を半分に絞り込むことを繰り返しながら、目的のデータを発見する手法です。

まず、対象のデータ列（配列など）の中央にあるデータが目的のデータであるかを確認します。それが目的のデータでない場合には、目的のデータと比べて小さいか大きいかを調べ、目的のデータが前半部分にあるのか後半部分にあるのかを判断します。この判断のために、データ列がソートされている必要があります。また、中央にあるデータに効率よくアクセスできなければ大幅な速度低下を起こすことになるので、実質的にランダムアクセスが可能であることも前提条件です（たとえば連結リストを二分探索するのは非効率ということになる）。

目的のデータが前半部分にあるとわかったのなら、後半部分をまるごと探索範囲から除外することができます。反対に、後半部分にあるとわかったなら前半部分を除外できます。この手順を、目的のデータが見つかるか、探索範囲がなくなるまで繰り返します。

データを１回比較するごとに、探索範囲を約半分にまで減らすことができ、目的のデータの位置が急速に絞り込まれます。計算量でいえば、n個のデータがあるとき、平均して O(log n) です。

Ｃ言語による二分探索の解説が、アルゴリズムとデータ構造編【探索】第４章にあります。