如何使用高级二进制搜索？

为什么以及如何？

当我在 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中文网其他相关文章！