153. 寻找旋转排序数组中的最小值
LeetCode 1531 · 中等 · 二分查找
题
一个元素互不相同的升序数组被旋转了若干次（如 [0,1,2,4,5,6,7] 变成 [4,5,6,7,0,1,2]，也可能转回原样），返回其中的最小值。要求 \(O(\log n)\)。
例：nums = [3, 4, 5, 1, 2] → 1；nums = [11, 13, 15, 17] → 11。
一句话
后段每个数都 <= nums[-1]，前段每个数都 > nums[-1]——这个谓词单调，最小值就是后段的起点，一个 lower_bound 找出来。
关键技巧
二分不需要数组有序，只需要谓词单调。 旋转数组 = 大的前段 + 小的后段，后段以 nums[-1] 结尾。定义
\[ P(i) = [\,nums_i \le nums_{n-1}\,] \]
前段所有元素都大于后段所有元素，自然大于 \(nums_{n-1}\)，所以前段全 F；后段升序且以 \(nums_{n-1}\) 收尾，全 T。谓词形如 F…F T…T，第一个 T 就是最小值。没旋转时整个数组都是后段，答案是下标 0，同样成立。
区间不变量：左闭右开 \([lo, hi)\)，\([0, lo)\) 全 F，\([hi, n)\) 全 T。因为 \(P(n-1)\) 一定为 T，可以直接从 hi = n - 1 开始（下标 \(n-1\) 已知为 T），循环结束 lo 就是答案，且一定合法。
为什么和 nums[-1] 比而不是 nums[0]：和 nums[0] 比，没旋转的数组会全是 T（>= nums[0]），分界点跑到 \(n\)，要特判。末尾元素在两种情况下都属于后段，无需特判。
解
class Solution:
def findMin(self, nums: List[int]) -> int:
lo, hi = 0, len(nums) - 1 # [lo, hi) 未知；下标 n-1 已知满足谓词
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] <= nums[-1]:
hi = mid
else:
lo = mid + 1
return nums[lo]
时间 \(O(\log n)\)，空间 \(O(1)\)。
延伸
- 有重复元素（LeetCode 154）：谓词不再单调（
[1,1,0,1]前后都有等于末尾的），改为与nums[hi]比，相等时hi -= 1，最坏 \(O(n)\)。 - 找到最小值下标就是断点，再按 target 与
nums[-1]的大小决定去前段还是后段做普通二分——这是 33. 搜索旋转排序数组 的两步解法。 - 同一个「谓词单调即可二分」的思想：34. 在排序数组中查找元素的第一个和最后一个位置、4. 寻找两个正序数组的中位数（在切分位置上二分）。
自测
-
LeetCode 153，2026-09-29 读。 ↩