RSS
探索アルゴリズムの一種で、データ列がソートされていることを利用して、探索対象範囲を半分に絞り込むことを繰り返しながら、目的のデータを発見する手法です。
まず、対象のデータ列（配列など）の中央にあるデータが目的のデータであるかを確認します。それが目的のデータでない場合には、目的のデータと比べて小さいか大きいかを調べ、目的のデータが前半部分にあるのか後半部分にあるのかを判断します。この判断のために、データ列がソートされている必要があります。また、中央にあるデータに効率よくアクセスできなければ大幅な速度低下を起こすことになるので、実質的にランダムアクセスが可能であることも前提条件です（たとえば連結リストを二分探索するのは非効率ということになる）。
目的のデータが前半部分にあるとわかったのなら、後半部分をまるごと探索範囲から除外できます。反対に、後半部分にあるとわかったなら前半部分を除外できます。この手順を、目的のデータが見つかるか、探索範囲がなくなるまで繰り返します。
データを１回比較するごとに、探索範囲を約半分にまで減らすことができ、目的のデータの位置が急速に絞り込まれます。計算量でいえば、n個のデータがあるとき、平均して O(log n) です。
Ｃ言語による二分探索の解説が、アルゴリズムとデータ構造編【探索】第４章にあります。
Ｃ言語の標準ライブラリに含まれる bsearch関数（Ｃ言語編のリファレンス）は、仕様上は明確に規定していないものの、一般的に二分探索を使った探索をおこなう関数になっています。
C++ の標準ライブラリ（STL）に含まれる std::binary_search関数（C++編【標準ライブラリ】第２３章）は、二分探索を実装した関数テンプレートです。
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |