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

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

题目描述

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

image-20260928193848680

image-20260928193848681

题意分析

一个原本严格升序、元素互不相同的数组，经过若干次首尾轮转后得到当前数组。需要返回其中的最小元素值，而不是它的下标，也不需要恢复排序。

旋转只改变分界位置，不改变各段内部顺序；转满一整圈时，数组也可能仍然整体升序。题目保证数组非空，并要求 $O(\log n)$ 时间，因此不能逐个扫描寻找最小值。

解法：二分定位旋转断点

核心思路

[!blue]

发生有效旋转时，数组由“较大的一段升序值”和“较小的一段升序值”拼接，最小值就是后段的开头；没有有效旋转时，最小值是首元素。虽然整个数组未必有序，这种只有一个下降分界的结构仍能帮助二分。

始终维护闭区间 [left, right]，保证最小值在其中。取下取整的中点 mid，与区间右端比较：若 nums[mid] > nums[right]，从中点到右端一定跨过了下降分界，所以最小值严格在中点右侧，令 left = mid + 1。

若 nums[mid] < nums[right]，从 mid 到 right 没有下降分界，是升序的一段。其中最小的就是 nums[mid]，更右侧的数都不可能成为全局最小值；答案可能是 mid，也可能在更左侧，因此令 right = mid，必须保留中点。

循环中 left < right，下取整保证 mid < right，加上元素互不相同，不会出现两者值相等的情况。两个分支都会缩小区间，同时不丢掉答案；最终只剩一个位置，它就是最小值。整体有序或只有一个元素的情况也适用，不需要单独找下降点。

解题步骤

  1. 初始化 left = 0、right = n - 1，候选区间覆盖整个非空数组。
  2. 在 left < right 时计算下取整中点 mid。
  3. 若 nums[mid] > nums[right]，最小值位于 [mid + 1, right]，更新左边界。
  4. 否则排除中点右侧的更大元素，令 right = mid，保留中点本身。
  5. 两端相遇后返回 nums[left]。

代码实现

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)$，只保存固定数量的下标。

关键点总结

[!green]

  • 利用旋转数组至多一个下降分界的结构，不要求整个搜索区间升序。
  • 中点比右端大时可以排除中点；中点比右端小时，中点本身仍可能是答案。
  • 区间始终包含最小值，结束条件是只剩一个候选，而不是查找到某个给定目标。
  • 元素互不相同保证比较能确定方向，这个前提不能省略。

易错点总结

[!yellow]

  • 中点比右端小时写成 right = mid - 1，会把恰好位于中点的最小值排除。
  • 仍用 left <= right 循环，却保留 right = mid，单元素区间可能不再缩小，导致死循环。
  • 只寻找严格下降的相邻位置，没处理数组整体升序的情况，会漏掉旋转整圈后的输入。
  • 用左端作参照却直接照搬这里的分支，可能错误处理未旋转区间；比较对象和排除依据需要配套。
  • 将这套严格二分直接用于含重复值的数组，相等时无法确定分界在哪一侧；那是第 154 题需要额外处理的情况。
  • 最终返回 left，得到的是下标；题目要求返回该位置的元素值。

相似题目

题目 难度 关联与区别
154. 寻找旋转排序数组中的最小值 II 困难 允许重复值后，比较相等可能无法确定最小值所在半区，需要退化缩边。
33. 搜索旋转排序数组 中等 同样利用旋转数组的单调结构，原题寻找指定值，本题只定位最小值。
81. 搜索旋转排序数组 II 中等 利用旋转数组中仍有序的一半排除搜索区间；本题比较中点与右端定位最小值，该题含重复值时处理无法判定有序侧的边界。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/88073281
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！