ITパスポート 試験情報＆徹底解説

探索アルゴリズムの一つで、ソート（整列）されたデータについて、探索範囲を半分に絞り込む操作を繰り返して探索を行なうもの。バイナリサーチとも呼ばれる。

具体的には、まず中央の要素と目的の要素を比較して、中央よりも前にあるか後ろにあるかを判断。前ならば、次は前半分の中から中央の要素を取り出して目的の要素を比較する。この作業を中央の要素が目的の要素と一致するか、探索範囲の要素が1つになるまで繰り返す。探索範囲の要素が1つになった場合は、目的の要素が見つからなかったことになる。

要素がN個ある場合、log₂N回の比較で探索が可能で、原理が単純な割には高速なアルゴリズムである。ただし、データがソートされていない場合や大小関係を定義できない場合には使えない。