如何使用進階二進制搜尋？

為什麼以及如何？

當我在 leetcode 上解決問題時，該問題說在給定的按非遞減順序排序的整數數組 nums 中，找到給定目標值的開始和結束位置。因此不可能用簡單的二進位 Sarch 來傳回數組中目標元素的開始和結束，因為它只傳回找到第一個目標元素的索引，該元素可以是該元素的第一個、結尾或中間的任何內容。所以我們使用 Double Binary Scarch ，具體方法如下...

方法

1. 第一次二分查找：

   • 執行二分搜尋以找出目標的最後一次出現。
   • 以 si（起始索引）從 0 開始，以 ei（結束索引）從 nums.length - 1 開始。
   • 如果中間元素nums[mid]小於目標，則將起始索引si移至mid + 1以在右半部搜尋。
   • 如果大於目標，則將結束索引ei移至mid - 1以在左半部搜尋。
   • 如果 nums[mid] 等於目標，則將 res[1] 設為 mid（範圍的當前末尾），並繼續在右半部 (si = mid + 1) 中搜尋以找到最後一次出現的位置。

2. 第二次二分查找：

   • 再執行另一次二分搜尋以找出目標的第一次出現。
   • 將 si 重設為 0，將 ei 重設為 nums.length - 1。
   • 遵循與之前類似的方法，但如果nums[mid] 等於目標，則將res[0] 設定為mid（範圍的當前開始）並繼續在左半部搜尋(ei = mid - 1)找到第一個出現的位置。

3. 回傳結果:

   • 結果陣列 res 包含目標值的起始和結束索引。

複雜

• 時間複雜度：

  • 二分找出第一次和最後一次出現的時間分別需要 O(log n) 時間。由於我們執行兩次二分搜索，因此總體時間複雜度為 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
    }
}

以上是如何使用進階二進制搜尋？的詳細內容。更多資訊請關注PHP中文網其他相關文章！