LeetCode 33. 搜索旋转排序数组

◎

本节目标

在无重复的旋转有序数组中识别有序半区并完成二分查找。

这道题把二分查找解题框架从整体有序扩展到局部有序：每轮至少有一半仍保持递增。

查看原题

题意与约束

数组由严格递增数组在某个位置旋转得到，元素互不重复。返回 target 的下标，不存在则返回 -1。

朴素思路与瓶颈

线性扫描不受旋转影响，却需要 O(n)；直接套普通二分又会错误地假设整个区间递增。旋转数组每轮至少有一半有序，因此应先识别有序半区，再根据目标值域排除另一半。

先找有序半区

比较 nums[left] 和 nums[mid]：

• 若 nums[left] <= nums[mid]，左半 [left, mid] 有序；
• 否则右半 [mid, right] 有序。

随后检查 target 是否落在这个有序半区的值域中。若落在，就保留它；否则保留另一侧。无重复约束保证不会出现“端点与中点相等、无法判断哪一侧有序”的歧义，因此每次排除都安全，且区间严格缩小。

代码实现

精确命中仍立即返回；其余情况只依据有序半区和值域范围更新边界。

C++

C++17

#include <vector>
using namespace std;

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

        while (left <= right) {
            const 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;
    }
};

Python

Python 3

class Solution:
    def search(self, nums, target):
        left = 0
        right = 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
            elif nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
        return -1

复杂度分析

• 时间复杂度：O(log n)。
• 空间复杂度：O(1)。

易错点

• 不要先线性寻找旋转点，那会丢掉对数复杂度。
• 判断左侧值域时，上界必须排除 mid，因为相等已在前面返回。
• 本题无重复；允许重复时不能沿用同一判断直接保证对数复杂度。

模式迁移

旋转数组最小值也依赖无重复带来的可判定性，但它不寻找目标，而是比较中点和右端点以保留断点。