なぜ、どのようにして?

私がleetcodeの質問を解いている間に、降順でない整数の指定された配列で、指定されたターゲット値の開始位置と終了位置を見つけるという内容でした。そのため、単純なバイナリ スカーチでは、配列内のターゲット要素の開始と終了を返すことは不可能でした。これは、最初のターゲット要素が見つかったインデックスのみを返すためであり、その要素の first 、 end 、または middle のいずれかになる可能性があります。そこで Double Binary Scharch を使用します。その方法は次のとおりです...

アプローチ

1. 最初の二分探索:

   • 二分検索を実行して、ターゲットの最後に出現したものを見つけます。
   • si (開始インデックス) は 0、ei (終了インデックス) は nums.length - 1 で始まります。
   • 中央の要素 nums[mid] がターゲットより小さい場合、開始インデックス si を mid 1 に移動して、右半分を検索します。
   • 目標より大きい場合、終了インデックス ei をmid - 1 に移動して左半分を検索します。
   • nums[mid] がターゲットと等しい場合は、res[1] をmid (範囲の現在の終わり) に設定し、右半分 (si = mid 1) で検索を続けて最後の出現箇所を見つけます。

2. 2 番目の二分探索:

   • 別のバイナリ検索を実行して、ターゲットの最初の出現を見つけます。
   • si を 0 にリセットし、ei を nums.length - 1 にリセットします。
   • 前と同様のアプローチに従いますが、nums[mid] がターゲットと等しい場合は、res[0] をmid (範囲の現在の開始点) に設定し、左半分 (ei = mid - 1) で検索を続けます。最初の出現箇所を検索します。

3. 戻り結果:

   • 結果配列 res には、ターゲット値の開始インデックスと終了インデックスが含まれます。

複雑

• 時間計算量:

  • 最初と最後の出現のバイナリ検索にはそれぞれ O(log n) 時間がかかります。 2 つのバイナリ検索を実行するため、全体の時間計算量は O(log n).
  になります。

• 空間の複雑さ:

  • O(1) 変数に固定量の追加スペースを使用しているためです。

コード

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int ei = nums.length - 1;
        int si = 0;
        int[] res = {-1, -1};  // Initialize result array

        // First binary search to find the last occurrence
        while (si  nums[mid]) {
                si = mid   1;
            } else {
                res[1] = mid;  // Update end index
                si = mid   1;  // Search in the right half
            }
        }

        // Reset the pointers for the second binary search
        si = 0;
        ei = nums.length - 1;

        // Second binary search to find the first occurrence
        while (si  nums[mid]) {
                si = mid   1;
            } else {
                res[0] = mid;  // Update start index
                ei = mid - 1;  // Search in the left half
            }
        }

        return res;  // Return the result array
    }
}