二分探索(バイナリサーチ)とは

二分探索とは、サーチアルゴリズムの一種です。リストや配列に入ったソート済のデータに対して、中央値を基準にどんどん探索範囲を絞って効率的に探索を行うアルゴリズムです。

n個のデータから1つのデータを見つけ出すのにかかる、時間計算量は O(log n) です。

大小関係の比較が定義できないデータや、未ソートのデータに対しては使用できないアルゴリズムですが、線形探索より効率的に探索できます。

アルゴリズムの解説

  1. 探索範囲内にデータが無ければ探索を終了します。
  2. 探索範囲のデータから中央値を取り出します。
  3. 取り出したデータが目的のデータかどうか比較します。
  4. 目的のデータに一致すれば探索完了です。
  5. 目的のデータより中央値が大きい場合、探索範囲の最大値を中央値まで狭めて 1. に戻る
  6. 目的のデータより中央値が小さい場合、探索範囲の最小値を中央値まで狭めて 1. に戻る
二分探索

探索対象のデータはソート済であるという前提なので 、中央値と比較すればそれ以上(以下)の値を探索範囲外として無視することができます。したがって、探索する範囲のインデックス最大値・最小値を 1/2 ずつ狭めていくことができます。

サンプルコード

見つかった要素のあるインデックスを返します。データが存在しなければ -1 を返すようにしています。

C#

public static int BinarySearch<T>(T[] array, T target) where T : IComparable<T>
{
    int min = 0;
    int max = array.Length - 1;

    while (true)
    {
        // 範囲内に見つからなかった
        if (max < min) return -1;
        // 範囲内の中央値と比較する
        int mid = min + (max - min) / 2;
        switch (target.CompareTo(array[mid]))
        {
            case -1:    // 中央値より小さい
                max = mid - 1;
                break;
            case 1:     // 中央値より大きい
                min = mid + 1;
                break;
            case 0:     // 見つかった
                return mid;
        }
    }
}