搜索旋转排序数组 II

标签: 数组 二分查找

难度: Medium

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

提示：

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -104 <= target <= 104

进阶：

  • 这是 搜索旋转排序数组 的延伸题目，本题中的 nums  可能包含重复元素。
  • 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

Submission

运行时间: 40 ms

内存: 15.4 MB

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        l = 0
        right = len(nums) - 1
        while right >= 1 and nums[right] == nums[0]:
            right -= 1

        r = right
        while l < r:
            mid = l + (r - l + 1) // 2
            if nums[mid] >= nums[0]:
                l = mid
            else:
                r = mid - 1

        if target >= nums[0]:
            r = l
            l = 0
        else:
            l += 1
            r = right

        while l <= r:
            mid = l + (r - l ) // 2
            if nums[mid] == target:
                return True
            elif nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1

        return False

Explain

该题解采用二分查找的思路。首先去除数组末尾与开头相等的元素,缩小搜索范围。然后通过二分查找定位旋转点的位置,将数组分为两个有序数组。最后根据目标值与开头值的大小关系,确定在哪一个有序数组中二分查找目标值。

时间复杂度: O(logn)

空间复杂度: O(1)

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        l = 0
        right = len(nums) - 1
        # 去除末尾与开头相等的元素
        while right >= 1 and nums[right] == nums[0]:
            right -= 1

        r = right
        # 二分查找旋转点
        while l < r:
            mid = l + (r - l + 1) // 2
            if nums[mid] >= nums[0]:
                l = mid
            else:
                r = mid - 1
        
        # 确定二分查找的区间
        if target >= nums[0]:
            r = l
            l = 0
        else:
            l += 1
            r = right
        
        # 二分查找目标值
        while l <= r:
            mid = l + (r - l ) // 2
            if nums[mid] == target:
                return True
            elif nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1

        return False

Explore

如果在去除数组末尾与开头相等的元素后数组变为空，意味着所有元素都是相同的，并且都等于数组的第一个元素。在这种情况下，只需要检查目标值是否与这个相同的元素相等。如果相等，则返回True，否则返回False。这种情况可以通过在二分查找开始之前添加一个检查来处理，如果数组长度为0，则直接根据目标值与数组第一个元素的比较结果返回。

在二分查找中使用`mid = l + (r - l + 1) // 2`的计算方式是为了确保当`l`和`r`非常接近时，`mid`能够偏向右侧，这有助于避免死循环并保证搜索范围能够稳定缩减。特别是在寻找旋转点的上下文中，这种方法能更精确地处理边界条件，确保不会漏掉旋转点的检测。

如果在确定旋转点后，`target`等于`nums[0]`，由于旋转排序数组的特性，`nums[0]`是旋转点左侧数组的最小元素，并且是右侧数组的最大元素。因此，如果`target`等于`nums[0]`，可以直接返回True，因为`nums[0]`是明确存在于数组中的。

使用`target >= nums[0]`而不是检查`target`是否在两个有序数组的范围内是因为，旋转排序数组分割成的两个部分之一始终包含数组的第一个元素`nums[0]`，并且这一部分数组是完全有序的。因此，只需检查`target`是否大于等于`nums[0]`来确定`target`是否可能位于这个有序部分。这简化了逻辑并减少了条件判断，使得算法更为高效和清晰。