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)``。线性扫描保留为从“找最小值”定义出发的 基线,二分主解利用严格递增、唯一断点和无重复三项信息,删除每轮不可能的一半候选。