153. 寻找旋转排序数组中的最小值 (Medium)
专题归类： 09-二分查找 LeetCode 链接： https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2] - 若旋转
7次，则可以得到[0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]。
给你一个元素值互不相同的数组 nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
示例 3：
输入：nums = [11,13,15,17]
输出：11
提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数互不相同nums原来是一个升序排序的数组，并进行了1至n次旋转
题目详细分析
数据范围含义：
n <= 5000：O(n) 也能过，但要求 O(log n)，必须二分。- 所有值互不相同：不需要处理重复值（有重复时见 154-寻找旋转排序数组中的最小值 II）。
问题本质：
- 旋转数组由两段递增序列组成：
[大段, 小段]。 - 最小值恰好是”小段”的第一个元素，也是整个数组的唯一”拐点”——即
nums[i] > nums[i+1]中的nums[i+1]。
数组没有旋转的特例：
- 如果旋转 n 次（即旋转了一整圈），数组恢复原样，
nums[0]就是最小值。 - 此时
nums[0] < nums[-1]（首元素小于末元素），可以作为特判依据。
核心比较对象：
- 找最小值时，用
nums[mid]和nums[right]比较，而不是nums[left]。 - 因为
nums[mid] > nums[right]说明最小值在右半；nums[mid] < nums[right]说明最小值在左半（含 mid）。
小白版直白理解
就像一根有序的晾衣杆被人从某个点折弯了，变成”<“形。你要找到那个”折点”——也就是最小值的位置。
比如 [4,5,6,7,0,1,2]，就像一根晾衣杆：
7
6
5
4
2
1
0
那个”谷底” 0 就是最小值。
比较 mid 和 right：如果 mid > right，说明 mid 在大段，最小值在右边（向右边找）；如果 mid < right，说明 mid 在小段，最小值在左边或就是 mid（向左找）。
解题思路
思路一：二分比较 nums[mid] 和 nums[right]（推荐）
核心思想： 维护搜索区间 [left, right) 左闭右开。比较 nums[mid] 和 nums[right]（不是 left！）决定搜索方向。
算法流程：
- 初始化
left, right = 0, len(nums) - 1。 - 当
left < right时循环：mid = left + (right - left) // 2- 如果
nums[mid] > nums[right]：最小值在右半，left = mid + 1。 - 如果
nums[mid] < nums[right]：最小值在左半（包含 mid），right = mid。
- 循环结束时，
left == right，返回nums[left]。
为什么和 nums[right] 比较而不是 nums[left]：
- 最小值必定在”断点”处，而断点的特点是左侧元素都大于右侧所有元素。
nums[mid] > nums[right]意味着 mid 在断点的左侧（大段），收缩左边界。nums[mid] < nums[right]意味着 mid 在断点的右侧（小段），收缩右边界。
搜索过程可视化（以 nums=[4,5,6,7,0,1,2] 为例）：
初始: left=0, right=6, [4,5,6,7,0,1,2]
第1步: mid=3, nums[3]=7 > nums[6]=2, 左半是大段, left=4
第2步: left=4, right=6, [0,1,2]
mid=5, nums[5]=1 < nums[6]=2, 右半是小段, right=5
第3步: left=4, right=5, [0,1]
mid=4, nums[4]=0 < nums[5]=1, right=4
第4步: left=4, right=4, 退出
返回 nums[4]=0
def findMin(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
# mid 在大段，最小值在右半
left = mid + 1
else:
# mid 在小段，最小值在左半（含 mid）
right = mid
# left == right == 最小值位置
return nums[left]思路二：带特判的二分
核心思想： 先判断数组是否已经有序（没有旋转），如果是则直接返回 nums[0]。
def findMin(nums):
# 特判：没有旋转或旋转 n 次（恢复原序）
if nums[0] <= nums[-1]:
return nums[0]
left, right = 0, len(nums) - 1
while 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)
易错点
- 循环条件用
left < right而不是<=：因为当left == right时就找到了最小值，循环应该停止。如果用<=会陷入死循环。 nums[mid] > nums[right]时left = mid + 1：因为 mid 在大段，mid 本身不可能是最小值，可以跳过。nums[mid] < nums[right]时right = mid：因为 mid 可能在小段且可能就是最小值，所以不能跳过（不能mid - 1）。- 不是和
nums[left]比较：如果和nums[left]比较，nums[mid] > nums[left]无法区分 mid 在大段还是小段（因为小段也可能大于 left）。和nums[right]比较才能正确判断。 - 降序数组特例：虽然题目保证原数组是升序排列的，但如果考虑所有情况，升序旋转 + 无重复是最安全的条件。
框架提炼
旋转数组找最小值模板：
def findMin(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
left = mid + 1 # 最小值在右半，跳过 mid
else:
right = mid # 最小值在左半（含 mid）
return nums[left]关键区别：33 题 vs 153 题
| 问题 | 目标 | 比较对象 | 更新策略 |
|---|---|---|---|
| 33-搜索旋转排序数组 | 找 target | nums[left] vs nums[mid] | 判断哪段有序 |
| 153-寻找最小值 | 找最小值 | nums[mid] vs nums[right] | 判断最小值在哪段 |
记忆要点：
- 找最小值 → 和 right 比。
- 找 target → 和 left 比（判断哪段有序）。
while left < right→ 最终位置在 left/right 重合处。nums[mid] > nums[right]→ left = mid + 1（大段向右找）。nums[mid] < nums[right]→ right = mid（小段向左找，含 mid）。
关联题目
- 33-搜索旋转排序数组 — 同一类旋转数组问题，目标不同（找 target vs 找最小值），比较对象不同（和 left 比 vs 和 right 比），是完美的对比学习组合。
- 154-寻找旋转排序数组中的最小值II — 包含重复元素的版本，当 nums[mid] == nums[right] 时无法判断，需要 right -= 1 缩小范围。
- 35-搜索插入位置 — 标准二分查找基础，掌握后再学旋转数组变体更轻松。
- 81-搜索旋转排序数组II — 含重复元素的旋转数组搜索，与 154 题同一个升级方向。