Advanced Binary Scharch の使用方法?

なぜ、どのようにして？

私が 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 <= ei) {
            int mid = si + (ei - si) / 2;
            if (target < nums[mid]) {
                ei = mid - 1;
            } else if (target > 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 <= ei) {
            int mid = si + (ei - si) / 2;
            if (target < nums[mid]) {
                ei = mid - 1;
            } else if (target > 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
    }
}

以上がAdvanced Binary Scharch の使用方法?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。