搜索旋转排序数组

难度: 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,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1], target = 0
输出：-1

提示：

1 <= nums.length <= 5000
-10⁴ <= nums[i] <= 10⁴
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10⁴ <= target <= 10⁴

Submission

运行时间: 44 ms

内存: 15.1 MB

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)-1
        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 = len(nums) -1

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

        return -1

Explain

这个题解的思路是先通过二分查找找到旋转点，将数组分为两个有序的子数组。然后根据目标值和第一个元素的大小关系，确定在哪个子数组中进行二分查找。最后在选定的子数组中进行标准的二分查找，找到目标值的下标或确定目标值不存在。

时间复杂度: O(log n)

空间复杂度: O(1)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 第一次二分查找，找到旋转点
        l = 0
        r = len(nums)-1
        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 = len(nums) -1
        
        # 在选定的子数组中进行二分查找
        while l <= r:
            mid = l + (r - l ) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        
        # 目标值不存在于数组中
        return -1

Explore

在旋转排序数组中找到旋转点的关键是确定哪一部分是有序的。初始时，我们比较中间元素与数组的第一个元素。如果中间元素大于等于第一个元素，说明从第一个元素到中间元素之间的子数组是有序的，旋转点应该在中间元素的右侧或就是中间本身。反之，如果中间元素小于第一个元素，旋转点应在左侧。通过不断缩小查找范围，最终左指针 l 将指向旋转点。

目标值的定位是基于旋转点和目标值与第一个元素的比较来决定的。如果目标值大于等于第一个元素，搜索范围是从数组开始到旋转点；如果目标值小于第一个元素，搜索范围是从旋转点的下一个位置到数组末尾。即使在极端的旋转情况（如旋转一位或旋转 n-1 位），这种方法仍然有效，因为旋转点的定位将正确划分两个有序的子数组。

虽然可以直接在整个旋转数组上使用一种变体的二分查找来寻找目标值，但这通常需要更复杂的条件判断来处理旋转的特性，增加了实现的复杂度和出错的可能性。通过首先找到旋转点，然后在确定的有序子数组上应用标准的二分查找，可以简化问题并利用二分查找的高效性。这种方法更直观，也更容易维护和理解。

使用 `(r - l + 1)` 的目的是在计算中值时向上取整，这样可以保证在 l 和 r 非常接近时，mid 能够向右偏移，从而避免在一些情况下陷入死循环。比如当 l 和 r 相等时，如果使用 `(r - l)` 计算，mid 将等于 l，可能导致无法进一步缩小查找范围。使用向上取整的方式，可以确保在所有情况下 l 和 r 都能有效地向旋转点靠拢，最终准确定位。