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

挨个比当然能找到最小，可那是 O(n)，白白浪费了「旋转前本来有序」。题目把有序明牌摆这了，得用二分把它砍到 O(log n)。

转折：最小值就是旋转点。怎么二分定位它？ 拿 nums[mid] 和右端点 nums[r] 比——这是 不变量：若 nums[mid] ＞ nums[r]，说明从 mid 到 r 中间有断崖， 最小值在 mid 右边（l=mid+1）；若 nums[mid] ＜ nums[r]，说明 mid 到 r 已经是连续升序， 最小值在 mid 或它左边（r=mid，别丢 mid）。为什么不和 nums[l] 比？因为左半整段可能都比最小值大，比左端判不出方向。

准备 · 闭区间 [0,6]：搜索范围是整个数组，l=0、r=6。比较的「锚」永远是当前的右端 nums[r]。

第 1 轮 · 取 mid：中点 mid=3，nums[3] = 7。和右端点 nums[6]=2 比。

第 1 轮 · 判断（负例分支）：7 ＞ 2，说明从 mid 走到 r 中间一定 掉过崖（旋转点在右半），最小值在 mid 右边，且 mid 本身肯定不是最小。

第 1 轮 · 收缩：l 跳到 mid+1=4，左半 [4,5,6,7]（灰）整段丢掉——这半里没有最小值。范围缩到 [4, 6]。

第 2 轮 · 取 mid：范围 [4,6]，新中点 mid=5，nums[5] = 1。继续和右端 nums[6]=2 比。

第 2 轮 · 判断：1 ＜ 2，说明从 mid 到 r 是 连续升序（没掉崖），那这段最小的就在 mid 这头。最小值在 mid 或它左边，mid 可能就是答案。

第 2 轮 · 收缩：r 收到 mid=5（ 不是 mid−1，因为 mid 自己可能就是最小）。下标 6 丢掉，范围 [4, 5]。

第 3 轮 · 取 mid：范围 [4,5]，mid=4，nums[4] = 0。和右端 nums[5]=1 比。

第 3 轮 · 收缩 → l==r：0 ＜ 1，最小值在 mid 或其左，r 收到 4。现在 l == r == 4，区间只剩一个，循环结束。

答案：l 和 r 撞在下标 4，nums[4] = 0 就是最小值。每轮砍一半，O(log n) 搞定。

旋转找最小，记死一句：和右端点比。大于则断崖（最小值）在右，否则在左含 mid。和 nums[l] 比会判错，因为左半可能整段偏大。

边界三连：三种边界先想清楚。

面试官常追问：三个高频追问，答法记牢。