為什麼以及如何？

當我在解決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  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
    }
}