二分探索 【binary search】 2分探索 / バイナリサーチ

概要

二分探索（binary search）とは、データ検索アルゴリズムの一つで、一定の順序にソート(整列)済みのデータ群の探索範囲を半分に絞り込むを操作を繰り返すことで高速に探索を行う手法。

まず、データを降順（大きい順）あるいは昇順（小さい順）に並べ替え、探索したいデータが中央の要素より大きいか小さいかを調べる。これにより、データが全体の前半分にあるか後ろ半分にあるかを判定することができるため、存在しない側の半分は探索範囲から外すことができる。

半分になったデータ群の中央の要素と再び比較し、前半と後半のどちらにあるかを調べる。この操作を繰り返し行うことで、一回の操作ごとに探索範囲の大きさが半分になっていき、中央の要素が求めるデータに一致するか、探索範囲の要素数が一つになる（求めるデータは見つからなかったことが確定する）と探索は終了する。

値の大小は文字の索引順の前後関係などに適宜置き換えることにより、順序と比較手段を定義できればどのようなデータにも適用することができる。

n個のデータ群から平均でlog₂n回の比較で探索を終えることができ、例えば1000個のデータを10回の比較で探索できる。原理は単純ながら高速なアルゴリズムである。ただし、要素があらかじめ整列済みである必要があるため、未整列のデータに適用するにはソートの分の計算時間も必要となる。

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。