二分探索法（バイナリサーチ） - Algoful

二分探索(バイナリサーチ)とは 二分探索とは、サーチアルゴリズムの一種です。リストや配列に入ったソート済のデータに対して、中央値を基準にどんどん探索範囲を絞って効率的に探索を行うアルゴリズムです。 n個のデータから1つのデータを見つけ出すのにかかる、時間計算量は O(log n) です。 大小関係の比較が定義できないデータや、未ソートのデータに対しては使用できないアルゴリズムですが、線形探索より効率的に探索できます。 アルゴリズムの解説 探索範囲内にデータが無ければ探索を終了します。 探索範囲のデータから中央値を取り出します。 取り出したデータが目的のデータかどうか比較します。 目的のデータに一致すれば探索完了です。 目的のデータより中央値が大きい場合、探索範囲の最大値を中央値まで狭めて 1. に戻る 目的のデータより中央値が小さい場合、探索範囲の最小値を中央値まで狭めて 1. に戻る 探