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

约 4 分钟
文章信息 18 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 50-100 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 拼多多 虾皮 LeetCode 热题 100 面试经典 150 题
标签
数组 二分查找 旋转数组问题
目录

题目描述

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

image-20230304225649534

题意分析

一个升序数组被「旋转」了若干次：把前面一段整体搬到末尾。要求返回其中的最小元素，且题目明确要求 $O(\log n)$ 时间——这是在提示不能线性扫描。

关键约束是元素互不相同。这保证任意两个位置的比较都能得出严格的大小关系，不会出现「相等、无法判断」的情况，是对数做法能成立的前提。

两个必须想到的边界：其一，旋转 n 次等于没转，数组可能本身就是完全升序的，最小值在下标 0；其二，数组可能只有一个元素。任何做法都要在这两种输入下正确。

旋转后的数组由两段升序段拼成（或退化为一段），前一段的所有元素都大于后一段的所有元素，最小值正是第二段的起点。

解法：二分定位旋转断点

核心思路

问题关键：旋转数组由两段升序区间组成，最小值是两段的分界点。题目要求 $O(\log n)$，因此要用二分定位这个分界点，而不是线性找下降位置。

为什么与右端点比较：若 nums[mid] > nums[right]，mid 位于左侧较大的区间，最小值严格在它右边；否则 mid..right 有序，最小值在 mid 或其左边。与左端点比较在数组未旋转时容易产生歧义。

不变量与正确性：最小值始终位于闭区间 [left, right]。前一种情况能排除 mid，所以令 left = mid + 1；后一种情况 mid 仍可能是答案，所以令 right = mid。区间不断缩小，最终相遇位置只能是最小值。

解题步骤

  1. 初始化闭区间 [left, right] = [0, n-1]，答案一定在其中。
  2. 当 left < right 时取中点 mid。
  3. 若 nums[mid] > nums[right]，最小值只可能在 [mid+1, right]，更新 left = mid + 1。
  4. 否则最小值位于 [left, mid]，更新 right = mid，注意保留 mid。
  5. left == right 时返回 nums[left]。以 [4,5,6,7,0,1,2] 为例，区间依次收缩为 [4,6]、[4,5]、[4,4]。

代码实现

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

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

        return nums[left];
    }
}

func findMin(nums []int) int {
    left := 0
    right := len(nums) - 1

    for 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 不可能是答案时才能写 mid + 1；否则必须保留 mid。
  • while (left < right)、下取整中点和 right = mid 是配套模板，不会产生空区间或死循环。
  • 若元素可重复，nums[mid] == nums[right] 时只能 right--，最坏会退化为 $O(n)$，这就是 154 题的区别。

易错点总结

  • 与左端点比较后直接排除一半：未旋转的 [1,2,3] 很容易被误判，右端点才是这套判断的稳定参照。
  • nums[mid] < nums[right] 时写 right = mid - 1：在 [3,1,2] 中会丢掉答案 nums[mid] = 1。
  • 循环使用 left <= right，同时仍写 right = mid：当区间只剩一个元素时无法收缩，会死循环。
  • 把条件写成 >= 并照搬到含重复元素的题：相等时无法判断最小值在哪边，不能直接舍弃一半。
  • 中点写成 (left + right) / 2 有整数溢出风险，应写 left + (right-left)/2。

相似题目

题目 难度 考察点
33. 搜索旋转排序数组 中等 找目标值而非最小值，先判有序半边再定方向
81. 搜索旋转排序数组 II 中等 33 的重复元素版，相等时收缩端点、最坏 $O(n)$
154. 寻找旋转排序数组中的最小值 II 困难 本题的重复元素版，nums[mid] == nums[right] 时 right--
剑指 Offer 11. 旋转数组的最小数字 简单 与 154 同题，含重复元素的最小值查找
面试题 10.03. 搜索旋转数组 中等 有重复且要求返回最小下标，条件分支更繁琐