为什么以及如何？

当我在解决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
    }
}