C#で二分探索のアルゴリズムを書いてみる。

二分探索とは？

二分探索（Binary Search）とは、ソート済みの配列やリストから、探索対象の値を効率的に検索するアルゴリズムのことです。

配列を半分に分割し、探索対象の値が左側の配列にあるか右側の配列にあるかを判断して、次に探索する範囲を半分に狭めていく方法です。これにより、検索対象の数が大きい場合でも、従来の線形探索よりも高速に探索することができます。

二分探索のアルゴリズムは以下のように表されます。

1. 探索対象の値をtargetとする
2. 配列の中央の要素を指定するmidを計算する
3. targetとmidを比較する
   • targetとmidが等しい場合、探索を終了してmidを返す
   • targetがmidよりも小さい場合、配列の左半分を探索するためにrightをmid-1に設定する
   • targetがmidよりも大きい場合、配列の右半分を探索するためにleftをmid+1に設定する
4. leftがrightよりも大きくなるまで、2から3を繰り返す

例文

sample.cs

static int BinarySearch(int[] array, int target) {
    int left = 0;
    int right = array.Length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (array[mid] == target) {
            return mid;
        }
        else if (array[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    return -1; // ターゲットが見つからなかった場合
}

上記のコードでは、BinarySearchメソッドを定義し、探索対象の配列と探索する値を引数に取っています。leftとright変数は、探索対象の範囲を示すポインタです。whileループは、配列の範囲が縮小されるたびに繰り返されます。mid変数は、配列の中央インデックスを示し、その値を使って探索対象の範囲を更新します。if文は、配列の中央値と探索値を比較して、探索範囲を縮小するためにleftとrightの値を更新します。もしtargetが見つからなかった場合は、-1を返します。