0153. Find Minimum in Rotated Sorted Array¶
题目信息¶
- 题号:
寻找旋转排序数组中的最小值
- 难度:
Medium
- 主题:
数组、二分查找、旋转有序结构、区间不变量
- 原题:
- 重点:
用右端值判断中点属于高值段还是低值段,并根据中点能否成为最小值决定开闭区间更新
题目重述¶
一个元素互不相同的严格递增数组经过若干次旋转:每次把末尾元素移到开头。给定旋转后的非空数组
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]:
区间 |
|
新区间 |
|---|---|---|
|
|
最小值严格在右侧,改为 |
|
|
保留中点及左侧,改为 |
|
|
改为 |
若数组未旋转,例如 [-6,-1,3,9],每次都是 nums[middle] < nums[right],右边界持续左移,最终
自然落到下标零,不需要预先特判“已经有序”。
收敛与边界正确性¶
两个分支都保持最小值在闭区间内,并让区间严格缩短:第一分支令左边界越过中点,第二分支令右边界到中点。
当 left == right 时,不变量说明唯一剩余下标就是最小值。单元素数组跳过循环,使用同一结论直接返回。
公开入口采用二分方案,时间 O(log n)、额外空间 O(1)。线性扫描保留为从“找最小值”定义出发的
基线,二分主解利用严格递增、唯一断点和无重复三项信息,删除每轮不可能的一半候选。