IT用語入門：2分探索法【整列データを半分ずつ絞って探す】

2分探索法とは

2分探索法は、あらかじめ整列されたデータから目的の値を効率よく見つける探索アルゴリズムです。バイナリサーチとも呼ばれ、検索対象の範囲を毎回半分に狭めながら探していくのが特徴です。

イメージとしては、昇順に並んだ電話帳で目的の名前を探すときに、まず真ん中あたりを開いて、探したい名前が前か後ろかを判断する方法に近いです。大まかに位置を絞り、不要な半分を捨てる操作を繰り返します。

仕組みは単純で、現在の探索範囲の中央要素を取り出して目的の値と比較します。目的が中央より小さければ前半に、大きければ後半に範囲を絞り、見つかるか範囲が空になるまで続けます。整列されていること、大小関係が定義できることが前提です。

比較回数は要素数Nに対しておおよそlog2 N回に抑えられ、単純ながら高速です。大量データの検索、辞書機能、しきい値や境界の判定などで活躍します。役割は、整列済みデータから少ない手数で目的の位置を特定することです。