myEsn2E9

[二分探索 binary search] は、分割統治法に基づく効率的な検索アルゴリズムです。データの順序性を利用し、各ラウンドで検索範囲を半分に減らしていきます。目標の要素が見つかるか、検索範囲が空になるまで続けられます。

まず、ポインターi=0とj=n-1を初期化し、配列の最初の要素と最後の要素を指すようにします。これは、検索範囲[0, n-1]を表しています。角括弧は閉区間を示し、境界値自体を含みます。

次に、以下の 2 つのステップを繰り返します：

1. 中央のインデックスm = \lfloor {(i + j) / 2} \rfloorを計算します。ここで、$\lfloor : \rfloor$ は切り捨て操作を表します。
2. nums[m]とtargetの大小関係を判断し、以下の 3 つの場合に分けます：
   1. nums[m] < targetの場合、targetは範囲 [m+1, j] にあるため、i=m+1 を実行します。
   2. nums[m] > targetの場合、targetは範囲 [i, m-1] にあるため、j=m-1 を実行します。
   3. nums[m] = targetの場合、targetが見つかったことを意味し、インデックス m を返します。

配列に目標の要素が含まれていない場合、検索範囲は最終的に空になります。この場合、-1 を返します。

注意すべき点は、i と j がint型であるため、i+j が型の範囲を超える可能性があることです。大きな数値のオーバーフローを避けるために、通常は中点を計算するために次の式を使用します：$m = \lfloor {i + (j - i) / 2} \rfloor$

/* 二分探索（閉区間） */
int BinarySearch(int[] nums, int target) {
    // 初期化：双閉区間[0, n-1]を指すようにiとjを設定
    int i = 0, j = nums.Length - 1;
    // 検索範囲が空になるまでループ
    while (i <= j) {
        int m = i + (j - i) / 2;   // 中点のインデックスmを計算
        if (nums[m] < target)      // nums[m] < targetの場合、範囲[m+1, j]にtargetがある
            i = m + 1;
        else if (nums[m] > target) // nums[m] > targetの場合、範囲[i, m-1]にtargetがある
            j = m - 1;
        else                       // 目標の要素が見つかった場合、インデックスmを返す
            return m;
    }
    // 目標の要素が見つからなかった場合、-1を返す
    return -1;
}

利点：時間と空間の面で優れたパフォーマンスがあります。

制約：

• ソートされたデータにのみ適用できます。入力データがソートされていない場合、二分探索を使用するためにデータをソートする必要があり、コストがかかります。
• 配列にのみ適用できます（連続したメモリ領域）。
• 小規模なデータでは、線形検索のパフォーマンスが優れています。アルゴリズム問題では、線形検索をハッシュ検索に置き換えて時間の計算量を削減することがよくあります。
  • 線形検索：時間を空間に対してトレードオフにする
  • ハッシュ検索：空間を時間に対してトレードオフにする

二分探索による挿入位置の検索：二分探索は、目標の要素を検索するだけでなく、目標の要素の挿入位置を検索するという多くの変種の問題にも適用できます。

二分探索による境界の検索：

1. 左境界の検索
2. 右境界の検索

線形検索は小規模または頻繁に更新されるデータに適しています。

二分探索は大規模でソートされたデータに適しています。

ハッシュ検索はクエリの効率が高く、範囲クエリが必要ないデータに適しています。

木構造による検索は、順序の維持と範囲クエリのサポートが必要な大規模な動的データに適しています。

参考#

• 第 10 章   検索 - Hello 算法 (hello-algo.com)