C#で二分探索（バイナリサーチ）を実装する方法｜仕組みと計算量を解説

二分探索とは

二分探索（バイナリサーチ）は、ソート済みの配列を対象とした高速な検索アルゴリズムです。探索したい値を配列の中央にある要素と比較し、一致しなかった場合は、その値が存在し得ない側の半分の領域を丸ごと除外します。この操作を残りの半分に対して繰り返すことで、効率よく目的の値を見つけ出します。

例えば、下図のような配列から「62」という値を探す場合を考えてみましょう。中央の要素との比較結果から、62が存在するのは右側の領域だけであることが分かるため、左半分は完全に除外され、以降は右半分のみが探索対象となります。

二分探索の計算量

二分探索における各ケースの計算量は以下の通りです。

データ件数が増えても探索回数は対数的にしか増加しないため、大量のデータを扱う場合でも非常に高速に動作するのが大きな特徴です。

C#での実装例

以下は、C#で二分探索を実装するサンプルコードです。

public static object BinarySearchDisplay(int[] arr, int key) {
    int minNum = 0;
    int maxNum = arr.Length - 1;

    while (minNum <= maxNum) {
        int mid = (minNum + maxNum) / 2;
        if (key == arr[mid]) {
            return ++mid;
        } else if (key < arr[mid]) {
            maxNum = mid - 1;
        } else {
            minNum = mid + 1;
        }
    }
    return "None";
}

このメソッドでは、まず探索範囲の最小インデックス minNum と最大インデックス maxNum を設定し、範囲が重ならなくなるまで次の手順を繰り返します。

• 中央のインデックス mid を求める
• 目的のキーが中央の要素と一致すれば、その位置を返す
• キーが中央の要素より小さければ、探索範囲を左半分に絞る
• キーが中央の要素より大きければ、探索範囲を右半分に絞る

最後まで見つからなかった場合は「None」を返します。なお、二分探索を正しく動作させるには、対象となる配列が必ず昇順にソートされている必要がある点に注意してください。