【LC 33 / 153】搜索旋转排序数组 & 最小值：同一道断崖，比较对象正好相反
- LC 33：整数数组
nums 经旋转后（如 [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]）搜索 target，要求 O(log n)，不存在返回 -1。
- LC 153：找出旋转数组中的最小值。美团社招面经原题即此题。
这两道题共享同一个画面：
旋转数组是两段各自上升的折线，中间一道断崖。最小值站在断崖右侧那段的起点上。二分查找它，每一步只需回答一个问题 ——
mid 站在断崖的哪一边？
有趣的是，两道题判断"哪一边"用的比较对象
正好相反，而各自都有充分的理由。这就是本篇的全部内容。
一、画面先行：断崖在哪，答案就在哪边
以
[4,5,6,7,0,1,2] 为例：
值: 4 5 6 7 | 0 1 2
第一段 ↗ | ↗ 第二段
↑
断崖（7 → 0）
- 153（找最小值）：最小值就是断崖右侧那段的起点。mid 要判断的是"我在断崖左边还是右边"；
- 33（搜 target）：mid 把区间切成两半，至少有一半完全有序（不含断崖）。在那半里做普通二分的值域判断即可。
1.1 LC 153 的判据：和 nums[right] 比
def findMin(nums):
l, r = 0, len(nums) - 1
while l < r:
mid = (l + r) // 2
if nums[mid] > nums[r]:
l = mid + 1 # mid 在第一段，断崖在右边
else:
r = mid # mid 在第二段，mid 可能就是最小值
return nums[l]
每一步的含义：
nums[mid] > nums[r]：mid 比当前区间末尾还大 —— 它右边一定跨过了断崖（否则这段递增到 r 也不会变小），所以最小值在 [mid+1, r]，mid 自己被淘汰；nums[mid] < nums[r]：mid 在断崖右侧的第二段上（或者断崖就是 mid），最小值在 [l, mid] 里 —— mid 可能就是答案，所以收缩是 r = mid 而不是 r = mid - 1。
循环条件
l < r：区间缩到 1 个元素时它就是答案。
1.2 为什么和 right 比，不和 left 比 —— 歧义从哪来
反过来想：如果和
nums[l] 比，
nums[mid] > nums[l] 时 mid 可能在第一段（断崖在右），
也可能整个数组没旋转（最小值就是
nums[l]）—— 两种情况这一个比较区分不了，下一步方向就无从谈起。
和 right 比没有这个歧义：
nums[mid] === nums[r] 只在区间缩到一两个元素时才可能发生（两段内部严格递增），不影响判断。
这个"比较对象的选择"就是本题的面试考点。 下一节会看到 33 用的是 left —— 因为它要的量不一样。
1.3 动画与逐帧推演
官方例
[4,5,6,7,0,1,2]（与状态机
rotatedMinSteps.js 的 5 帧实际输出逐行核对过）：
盯住第 2 帧：
nums[5] = 1 < nums[6] = 2 —— mid 在第二段上，最小值在
[4, 5] 里。如果这里写成
r = mid - 1 = 4，就把 mid 自己（正是最小值 1 的邻居、下一轮的关键候选）扔掉一半范围，整个算法直接失效。
"r = mid" 与 "r = mid - 1" 的一字之差，是这道题最经典的死法。
二、LC 33：和 nums[left] 比，找"有序的那半"
2.1 判据
mid 把
[l, r] 切成
[l, mid] 和
[mid, r] 两半，
断崖只在其中一半里，另一半完全有序。而"左半有序"有一个一步到位的判据：
nums[l] <= nums[mid] → 左半 [l, mid] 有序
nums[l] > nums[mid] → 右半 [mid, r] 有序
（等号重要：
l === mid 时区间只剩一两个元素，必须判"有序"。）
拿到有序的那半，就用一次
值域判断决定去哪边：
def search(nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
if nums[l] <= nums[mid]: # 左半有序
if nums[l] <= target < nums[mid]: # target 在左半值域内
r = mid - 1
else:
l = mid + 1 # 只可能在右半
else: # 右半有序
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
return -1
因为它们要的量不同：
- 153 要知道"mid 在断崖的哪一边" —— 这决定最小值在 mid 左边还是右边。和 right 比，
mid > right 就实锤 mid 在第一段，没有歧义；
- 33 要知道"哪一半有序" —— mid 把区间切成两半，左半有序当且仅当
nums[l] <= nums[mid]（左端不越过 mid）。和 left 比正好一步得到。
同一个断崖，两道题，比较对象正好相反 —— 不是巧合，是"你问的问题不同"。
2.2 值域判断的开闭边界
两个值域判断的端点一开一闭，各有一个理由：
- 左半值域
[nums[l], nums[mid])：右端开 —— target === nums[mid] 已在开头命中返回，走到这里说明不相等；
- 右半值域
(nums[mid], nums[r]]：两端都闭于 target 一侧 —— 左端开是同理，右端闭是因为 nums[r] 本身可以是 target。
写错任何一端的开闭，都会在 target 恰好是端点值时丢解。单测里专门放了
target = 4（第一段左端点）和
target = 2（第二段右端点）两个边界。
2.3 动画与逐帧推演
[4,5,6,7,0,1,2]，
target = 0（与状态机
rotatedSearchSteps.js 的 5 帧逐行核对过）：
第 1 帧值得多看一眼：左半
[0,3] 有序，值域
[4, 7)，target 0 不在 ——
哪怕右半是断崖那侧，target 也只可能在右半。"进无序的那半"听起来冒险，其实有序半的值域判断已经把另一半的可能性证明完了：target 若在左半，就必须落在它的值域里；不在值域里，就只剩右半。
三、两个必踩的坑
坑一：153 的 r = mid 写成 r = mid - 1。 1.1 节讲过 —— mid 可能就是最小值。配套的循环条件必须是
l < r（不是
l <= r，否则缩到相邻两个时死循环）。
坑二：33 的有序判断漏了等号。 nums[l] < nums[mid] 写成严格小于：区间缩到
l === mid（一两个元素）时判断为"左半无序"→ 走右半逻辑 → 但右半此时只有 mid 自己，值域判断用
nums[mid] < target <= nums[r] —— 方向彻底错乱。
等号是"单元素区间也算有序"的保证。
还有一个高频追问：
为什么 33 里 nums[l] <= nums[mid] 不怕没旋转的情况？ 没旋转时每一步都是左半有序，值域判断正常工作 —— 旋转只是让"哪半有序"换了位置，判断框架一个字没变。153 同理：没旋转时 mid 永远小于 right，一路
r = mid 往左缩，最后停在
nums[0] —— 退化成"找头"，但正确性和复杂度都不变。
四、复杂度
对比线性扫描 O(n)：旋转数组的信息量（两段有序）足以支撑二分 —— 这也是两题题面都点名 O(log n) 的原因。但要清醒：这个 O(log n) 依赖
元素互不相同（33/153 的题面保证），一旦允许重复，见第五节。
五、重复元素版本：81 / 154
元素可以重复时，两题各升级一档，而且都
只坏在一种情况：
- LC 81（重复版 33）：
nums[l] === nums[mid] 时无法判断哪半有序（两半都可能）—— 唯一安全的动作是 l += 1 丢掉一个确定不是 target（如果 target === nums[l] 早命中了）的元素。最坏（全是同一个元素）退化成 O(n)，平均仍 O(log n)；
- LC 154（重复版 153）：
nums[mid] === nums[r] 时无法判断断崖方向 —— 唯一安全的动作是 r -= 1：即使 nums[r] 是最小值，nums[mid] 与它相等，丢掉 r 也丢不掉答案的值。同样最坏 O(n)。
这两行 l += 1 / r -= 1 是旋转二分在重复元素下仅存的"确定性动作" —— 面试说出"为什么只能这样退、什么时候退化成 O(n)"，比写出无重复版本值钱。
六、Java 版
// LC 153
class Solution {
public int findMin(int[] nums) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r) >>> 1;
if (nums[mid] > nums[r]) l = mid + 1; // mid 在第一段
else r = mid; // mid 在第二段，不能丢
}
return nums[l];
}
}
// LC 33
class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = (l + r) >>> 1;
if (nums[mid] == target) return mid;
if (nums[l] <= nums[mid]) { // 左半有序
if (nums[l] <= target && target < nums[mid]) r = mid - 1;
else l = mid + 1;
} else { // 右半有序
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}
}
七、边界情况与常见坑
坑一：153 的 r = mid 与循环条件配套。 r = mid 配
l < r；写成
r = mid - 1 配
l <= r 是另一个（错误）算法 —— 会跳过最小值。
坑二：33 的 l <= r 循环条件。 33 是"命中即返回"的普通二分框架，用
l <= r；153 是"缩到一点"的框架，用
l < r。两题循环条件不同不是笔误，是终止语义不同。
坑三：mid 取整方向。 (l + r) / 2 向下取整在
r = mid 的框架里安全（不会死循环）；如果某天写
r = mid - 1 框架配向下取整的 mid，相邻两元素时
mid === l，收缩后区间不变 → 死循环。（Java 用
>>> 1 防溢出。）
坑四：target 恰好是端点值。 2.2 节的开闭边界 —— 自测用例必须包含"target = 第一段左端点"和"target = 第二段右端点"。
八、变体
一图流：
无重复 → 33/153 的 O(log n)；有重复 → 81/154 的"相等就退一格"，最坏 O(n)。
九、面试怎么答
- 先画图：两段上升折线 + 断崖，最小值在断崖右侧段起点 —— 画面立住了，判据都是推出来的；
- 153：和
nums[r] 比，r = mid 不是 mid - 1，循环条件 l < r；
- 33：和
nums[l] 比（带等号）找有序半，值域一开一闭；
- 主动对比：同一道断崖，两题比较对象相反，因为要的量不同（mid 在断崖哪边 vs 哪半有序）—— 这句是面试的分水岭；
- 自测：
findMin([4,5,6,7,0,1,2]) == 0；search([4,5,6,7,0,1,2], 0) == 4、search([4,5,6,7,0,1,2], 3) == -1、search([4,5,6,7,0,1,2], 4) == 0（左端点）、search([4,5,6,7,0,1,2], 2) == 6（右端点）；
- 一句话总结：旋转数组二分 = 普通二分 + 每步多问一句"mid 在断崖哪边"，答案就从比较对象的选择里长出来。
系列上一篇：【LC 56】合并区间。本文两段动画（各 5 帧），与状态机单测（153：15 例，33：20 例，各与线性参考解交叉验证）逐行核对过。