33. 搜索旋转排序数组

力扣题目链接 (opens new window)

题目描述

整数数组 nums 按升序排列，数组中的值互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [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，如果 nums 中存在这个目标值，则返回它的下标，否则返回 -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^4 <= nums[i] <= 10^4
• nums 中的每个值都互不相同
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

思路

看到有序数组，录友们应该先想到二分查找。

但本题数组被旋转过，例如 [4,5,6,7,0,1,2]，整体已经不是递增的了，不能再直接用普通二分的“nums[mid] 和 target 比大小”来决定方向。

那二分查找还能不能用？

可以。虽然整体不再有序，但每次取到 mid 后，[left, mid] 和 [mid, right] 中一定有一段是有序的。

为什么？

旋转点只有一个。它不可能同时落在 mid 的左边和右边，所以左右两段里，至少有一段没有跨过旋转点，仍然保持递增。

那么如何判断哪一段有序呢？

• 如果 nums[left] <= nums[mid]，说明左半区有序。
• 否则，右半区一定有序。

找到有序半区之后，就可以判断 target 是否落在这个值域中：

• target 在有序半区：保留这一半。
• target 不在有序半区：丢弃这一半，去另一边继续二分。

每轮都能确定丢弃一半元素，所以时间复杂度依然是 O(log n)。

很多录友会把“有序半区”判断出来，但边界写乱。这里一定要注意：本题数组元素互不相同，所以可以放心使用 <= 和范围比较。

模拟过程

以 nums = [4,5,6,7,0,1,2]、target = 0 为例。

初始化 left = 0、right = 6，mid = 3。此时 nums[left] = 4 <= nums[mid] = 7，左半区 [4,5,6,7] 有序。

但 target = 0 不在 [4,7] 的值域中，所以左半区不可能有答案，令 left = mid + 1 = 4。

现在 left = 4、right = 6，mid = 5。nums[mid] = 1 <= nums[right] = 2，说明右半区 [1,2] 有序。

target = 0 不在 [1,2] 内，因此答案只能在左侧，令 right = mid - 1 = 4。

最后 left = right = mid = 4，此时 nums[mid] 就是 0，直接返回下标 4。

想清楚以下几点，本题才算理解透彻：

• 不必找旋转点；每一轮只需要找到当前的有序半区。
• 有序半区不包含 target 时，可以被安全丢弃。
• nums[mid] == target 要先判断，命中后立刻返回。

解题代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;

            if (nums[left] <= nums[mid]) { // 左半区有序
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1; // target 在左半区
                } else {
                    left = mid + 1; // 左半区不可能有答案
                }
            } else { // 右半区有序
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1; // target 在右半区
                } else {
                    right = mid - 1; // 右半区不可能有答案
                }
            }
        }
        return -1;
    }
};

复杂度分析

时间复杂度：O(log n)，每一轮都丢弃一半搜索区间。空间复杂度：O(1)。

其他语言

Python3

class Solution:
    def search(self, nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid

            if nums[left] <= nums[mid]:  # 左半区有序
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:  # 右半区有序
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

Java

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;

            if (nums[left] <= nums[mid]) { // 左半区有序
                if (nums[left] <= target && target < nums[mid]) right = mid - 1;
                else left = mid + 1;
            } else { // 右半区有序
                if (nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
        }
        return -1;
    }
}

Go

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        }

        if nums[left] <= nums[mid] { // 左半区有序
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else { // 右半区有序
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
    return -1
}

JS

var search = function(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (nums[mid] === target) return mid;

        if (nums[left] <= nums[mid]) { // 左半区有序
            if (nums[left] <= target && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else { // 右半区有序
            if (nums[mid] < target && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
};

与代码随想录联系

本题的核心仍然是二分查找：每次根据条件排除不可能的区间。

如果录友对二分查找的循环边界还不熟悉，建议先看二分查找。这道基础题把 left、right 和 mid 的边界变化讲清楚了。

本题只是在普通二分查找上多了一步：先确定哪一半有序，再判断 target 是否在这一半的值域里。

把这道题和 704. 二分查找 放在一起刷，录友们就能更清楚地体会到，二分查找不是只能处理“整个数组都有序”的题目，而是利用每一轮都能排除一半答案的条件。