0153. Find Minimum in Rotated Sorted Array

题目信息

题号:
  1. 寻找旋转排序数组中的最小值

难度:

Medium

主题:

数组、二分查找、旋转有序结构、区间不变量

原题:

LeetCode 0153

重点:

用右端值判断中点属于高值段还是低值段,并根据中点能否成为最小值决定开闭区间更新

题目重述

一个元素互不相同的严格递增数组经过若干次旋转:每次把末尾元素移到开头。给定旋转后的非空数组 nums,返回最小元素。旋转整整数组长度后与原数组相同。目标时间复杂度为 O(log n)。

自建示例

  • [11, 14, 18, 2, 5, 8]:最小值 2 是低值有序段起点;

  • [-6, -1, 3, 9]:数组处于原严格递增顺序,最小值在下标 0;

  • [4]:搜索区间一开始就是单点,返回 4;

  • [3, 1, 2]:旋转断点紧邻开头,仍应返回 1。

C++ 实现

#include <algorithm>
#include <vector>

class Solution {
private:
    int scanEveryValue(const std::vector<int>& nums) {
        return *std::min_element(nums.begin(), nums.end());
    }

    int binarySearchForPivot(const std::vector<int>& nums) {
        int left = 0;
        int right = static_cast<int>(nums.size()) - 1;

        while (left < right) {
            const int middle = left + (right - left) / 2;
            if (nums[middle] > nums[right]) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }
        return nums[left];
    }

public:
    int findMin(std::vector<int>& nums) {
        return binarySearchForPivot(nums);
    }
};

题解

原始搜索与旋转后的两段结构

线性扫描所有元素当然能找到最小值,scanEveryValue 时间 O(n)。题目额外给出:原数组严格递增, 旋转后至多出现一次下降断点。于是数组可以看成一个较大值递增段接一个较小值递增段,最小值是低值段第一 项;若没有可见断点,则整数组就是一个递增段,最小值在开头。

真正需要定位的不是任意最小值,而是这个唯一分界。每次比较都应判断中点在断点哪一侧,并删除不可能包含 分界的一段。

为什么选择与右端元素比较

维护闭区间 [left, right],不变量是最小值下标始终在其中。只要 left < right,向下取整得到的 middle 严格小于 right;又因为元素互不相同,两者不会相等。

若 nums[middle] > nums[right],middle 与 right 不可能处于同一段未跨断点的递增区间:同一 递增段中较早的中点应更小。断点因此必在 middle 右侧,最小值位于 (middle, right]。中点本身还 比右端大,明确不可能是最小值,所以更新 left = middle + 1,可以删除中点。

若 nums[middle] < nums[right],从 middle 到 right 没有跨越断点,是低值段的递增后缀, 其中最小的是 nums[middle]。全局最小值可能正是中点,也可能还在左侧,但不可能位于中点右边,所以 更新 right = middle,必须保留中点。

两个分支不对称的 +1 正来自“中点能否仍是答案”,不是二分模板的机械写法。

为什么不直接依赖左端比较

与左端比较也能设计正确算法,但分支语义更容易混合“左半是否有序”和“当前区间是否已经整体有序”。与 右端比较时,middle > right 精确表示断点仍在右侧;middle < right 则直接把右半判为未跨断点的 递增段。无重复保证消除了第三种相等情况,决策每轮都能删除约一半区间。

具体走读旋转数组

对 [11, 14, 18, 2, 5, 8]:

区间 [left,right]

middle 与比较

新区间

[0,5]

middle=2,18 > 8

最小值严格在右侧,改为 [3,5]

[3,5]

middle=4,5 < 8

保留中点及左侧,改为 [3,4]

[3,4]

middle=3,2 < 5

改为 [3,3],返回 2

若数组未旋转,例如 [-6,-1,3,9],每次都是 nums[middle] < nums[right],右边界持续左移,最终 自然落到下标零,不需要预先特判“已经有序”。

收敛与边界正确性

两个分支都保持最小值在闭区间内,并让区间严格缩短:第一分支令左边界越过中点,第二分支令右边界到中点。 当 left == right 时,不变量说明唯一剩余下标就是最小值。单元素数组跳过循环,使用同一结论直接返回。

公开入口采用二分方案,时间 O(log n)、额外空间 O(1)。线性扫描保留为从“找最小值”定义出发的 基线,二分主解利用严格递增、唯一断点和无重复三项信息,删除每轮不可能的一半候选。