LeetCode 153. 寻找旋转排序数组中的最小值

◎

本节目标

通过中点与右端点比较，二分保留旋转数组的最小值。

这道题沿用二分查找解题框架的局部有序思想，但答案不是某个给定目标，而是旋转断点处的最小值。

查看原题

题意与约束

给定由严格递增数组旋转得到、且元素互不重复的非空数组，返回最小元素。

朴素思路与瓶颈

遍历数组取最小值或寻找第一次下降都需要 O(n)。数组无重复时，中点与右端点的大小关系能判断最小值位于中点右侧，还是仍在包含中点的左侧，从而每轮排除一半。

与右端点比较

维护闭区间 [left, right]，其中始终包含最小值：

• nums[mid] > nums[right] 时，中点位于较大的左段，最小值必在右侧，令 left = mid + 1；
• 否则中点位于含最小值的右段，mid 本身仍可能最小，令 right = mid。

元素无重复使两种关系足以区分位置；若可以相等，nums[mid] == nums[right] 将无法唯一判断该丢弃哪侧。收敛时 left == right，它就是最小值位置。

代码实现

循环条件是 left < right，因而读取 nums[right] 始终有效，也不需要额外处理已旋转与未旋转两种情况。

C++

C++17

#include <vector>
using namespace std;

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = static_cast<int>(nums.size()) - 1;
        while (left < right) {
            const int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
};

Python

Python 3

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

复杂度分析

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

易错点

• 当中点小于右端点时不能丢掉 mid，它可能就是最小值。
• 两元素数组同样要由同一规则处理，不能依赖长度大于二。
• 本题输入非空；空数组不在平台约束内。

模式迁移

旋转数组题的关键是写出“断点仍在哪个区间”的证明，而不是把旋转结构还原成完整排序。