0153. Find Minimum in Rotated Sorted Array
==========================================
题目信息
--------
:题号: 0153. 寻找旋转排序数组中的最小值
:难度: 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++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
int scanEveryValue(const std::vector& nums) {
return *std::min_element(nums.begin(), nums.end());
}
int binarySearchForPivot(const std::vector& nums) {
int left = 0;
int right = static_cast(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& 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]``:
.. list-table::
:header-rows: 1
* - 区间 ``[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)``。线性扫描保留为从“找最小值”定义出发的
基线,二分主解利用严格递增、唯一断点和无重复三项信息,删除每轮不可能的一半候选。