问题描述

给你一个升序排列的整数数组nums,数组中的元素互不相同。在传递给函数之前,nums在预先未知的某个下标k上进行了旋转,使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]。例如,[0,1,2,4,5,6,7]在下标 3 处经旋转后可能变为[4,5,6,7,0,1,2]。

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

解题思路

这是一道经典的二分查找问题的变种。因为数组本身是升序的,但又经过了旋转,所以我们需要对传统的二分查找算法进行一些修改。

首先,我们来观察旋转后的数组,以[4,5,6,7,0,1,2]为例:

[4, 5, 6, 7, 0, 1, 2] ↑        ↑left     right

我们可以发现,数组从某个点(即旋转点)开始,左右两部分都是有序的。这个性质可以帮助我们确定接下来搜索的方向。

具体来说,当我们选择一个中点mid时,可能会遇到以下两种情况:

1.nums[mid]位于左半部分有序区间内。在这种情况下:•如果target位于[nums[left], nums[mid]]区间内,则我们应该将搜索范围缩小到左半部分,即将right更新为mid - 1;•否则,我们应该将搜索范围缩小到右半部分,即将left更新为mid + 1。2.nums[mid]位于右半部分有序区间内。在这种情况下:•如果target位于[nums[mid], nums[right]]区间内,则我们应该将搜索范围缩小到右半部分,即将left更新为mid + 1;•否则,我们应该将搜索范围缩小到左半部分,即将right更新为mid - 1。

接下来,让我们通过一个具体的例子来理解这个过程。假设我们要在数组[4, 5, 6, 7, 0, 1, 2]中搜索目标值0:

[4, 5, 6, 7, 0, 1, 2]    目标值 0 ↑        ↑left     right

1.首先,我们选取中点mid = (left + right) // 2 = 3,此时nums[mid] = 7。2.由于nums[left] = 4 <= nums[mid] = 7,说明nums[mid]位于左半部分有序区间内。3.目标值0不在[nums[left], nums[mid]]区间内,所以我们将搜索范围缩小到右半部分,即将left更新为mid + 1 = 4。

[4, 5, 6, 7, 0, 1, 2]    目标值 0             ↑     ↑            left  right

1.现在,我们选取新的中点mid = (left + right) // 2 = 5,此时nums[mid] = 1。2.由于nums[mid] = 1 < nums[right] = 2,说明nums[mid]位于右半部分有序区间内。3.目标值0不在[nums[mid], nums[right]]区间内,所以我们将搜索范围缩小到左半部分,即将right更新为mid - 1 = 4。

[4, 5, 6, 7, 0, 1, 2]    目标值 0             ↑ ↑           right            left

1.现在,我们选取新的中点mid = (left + right) // 2 = 4,此时nums[mid] = 0。2.由于nums[mid] = 0等于目标值,我们找到了目标值的下标,返回mid = 4。

代码实现

最直接的解法就是从头到尾遍历整个数组,逐个元素进行比较,直到找到目标值或者遍历完整个数组。这种解法的实现非常简单:

pythonCopy code
def search(nums: List[int], target: int) -> int:    for i in range(len(nums)):        if nums[i] == target:            return i    return -1

这个解法的时间复杂度是 O(n),其中 n 是数组的长度。在最坏情况下,我们需要遍历整个数组。虽然这个解法的效率不高,但在某些特定情况下(例如数组很小,或者目标值位于数组的前部),它可能比二分查找更快。

利用二分查找的情况，得到的代码如下：

def search(nums: List[int], target: int) -> int:    left, right = 0, len(nums) - 1
    while left <= right:        mid = (left + right) // 2
        if nums[mid] == target:            return mid
        # nums[mid] 位于左半部分有序区间        if nums[left] <= nums[mid]:            if nums[left] <= target < nums[mid]:                right = mid - 1            else:                left = mid + 1        # nums[mid] 位于右半部分有序区间        else:            if nums[mid] < target <= nums[right]:                left = mid + 1            else:                right = mid - 1
    return -1

复杂度分析

•时间复杂度:O(log n)。每次循环都将搜索范围缩小一半,因此时间复杂度是对数级别的。•空间复杂度:O(1)。只使用了常数级别的额外空间。

小结

通过对旋转数组的观察,我们发现虽然整个数组不再有序,但总有一部分是有序的。利用这个性质,我们可以根据目标值与有序部分的关系,决定接下来搜索的方向。这种思路巧妙地将二分查找应用到了旋转数组中,使得我们能够在对数时间内找到目标值。