题目描述
LeetCode 153 — 寻找旋转排序数组中的最小值 (Medium)
已知一个长度为 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]
每次旋转将最右边的元素移到最左边。数组中的元素互不相同。
请你找出数组中的最小元素，要求 O(log n) 时间复杂度。
示例 1：
- 输入：
nums = [3,4,5,1,2] - 输出：
1 - 解释：原数组为
[1,2,3,4,5]，旋转 3 次得到[3,4,5,1,2]。
示例 2：
- 输入：
nums = [4,5,6,7,0,1,2] - 输出：
0 - 解释：原数组为
[0,1,2,4,5,6,7]，旋转 4 次得到[4,5,6,7,0,1,2]。
示例 3：
- 输入：
nums = [11,13,15,17] - 输出：
11 - 解释：原数组为
[11,13,15,17]，旋转 4 次（等于数组长度），数组保持不变。
约束：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数互不相同nums原来是一个升序排序的数组，并进行了1至n次旋转
核心思路分析
关键观察
旋转排序数组有一个非常重要的性质：旋转后数组被分成两个各自有序的子数组，左边子数组的所有元素都大于右边子数组的所有元素。
左边任意元素 > 右边任意元素（因为原数组严格递增，且无重复）
我们要找的最小值，正是右边子数组的第一个元素。
二分搜索策略
既然要求 O(log n)，且数组部分有序，自然想到二分搜索。关键问题是：每次如何判断最小值在左半区间还是右半区间？
核心技巧：拿 nums[mid] 和 nums[right] 比较——因为最小值在「较小的那一半」，而 right 天然指向右侧元素。
nums[mid] > nums[right]：说明 mid 落在左边较大的子数组中，最小值一定在 mid 右侧 →left = mid + 1nums[mid] < nums[right]：说明 mid 落在右边较小的子数组中，最小值在 mid 或其左侧 →right = mid
为什么和 right 比，而不是和 left 比？
和 left 比较无法判断最小值方向。假设
nums[mid] > nums[left]，最小值既可能在 mid 右侧（数组确实被旋转过），也可能就是 left 本身（旋转 n 次，数组未变化）。而和 right 比——只要nums[mid] > nums[right]，最小值一定在右侧，二分方向是确定的。
边界细节
right = mid（而非 right = mid - 1）的原因是：当 nums[mid] < nums[right] 时，mid 本身可能就是最小值（即右边子数组的第一个元素），不能跳过。
mid 使用向下取整（(left + right) / 2），因为二分中只出现 right = mid，不会出现 left = mid，所以不会发生死循环。
特殊情况：旋转 n 次
比如 nums = [11, 13, 15, 17]：从头到尾 nums[mid] < nums[right]，一直执行 right = mid 向左收缩，最终 left == right 指向 nums[0]，得到最小值 11。
解法：二分搜索
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2; // 向下取整
if (nums[mid] > nums[right]) {
left = mid + 1; // 最小值在右侧
} else {
right = mid; // 最小值在左侧（含 mid 自身）
}
}
return nums[left]; // left == right，即最小值
}
复杂度： 时间 O(log n)，空间 O(1)。
执行过程（以 [4,5,6,7,0,1,2] 为例）：
| 步骤 | left | right | mid | nums[mid] | nums[right] | 判断 | 操作 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 7 | 2 | 7 > 2 | left = 4 |
| 2 | 4 | 6 | 5 | 1 | 2 | 1 < 2 | right = 5 |
| 3 | 4 | 5 | 4 | 0 | 1 | 0 < 1 | right = 4 |
最终 left == right == 4，nums[4] = 0 ✓
变式一：寻找最大值
将问题翻转——在同一个旋转排序数组中寻找最大值，即左边子数组的最后一个元素。
对称思路
找最小值时我们和 right 比，找最大值则对称地和 left 比——因为最大值在「左边较大的子数组」中。
nums[mid] > nums[left]：mid 在左边较大的子数组，最大值在 mid 或其右侧 →left = midnums[mid] < nums[left]：mid 在右边较小的子数组，最大值在 mid 左侧 →right = mid - 1
关键细节：mid 必须向上取整
由于出现了 left = mid，mid 必须使用向上取整（(left + right + 1) / 2），否则会死循环：
只剩两个元素 left = 0, right = 1 时：
- 向下取整 →
mid = 0 = left→left = mid = 0→ 区间未缩小 → 死循环 - 向上取整 →
mid = 1 = right→left = 1→ 区间缩小 → 退出
int findMax(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2; // 向上取整
if (nums[mid] < nums[left]) {
right = mid - 1; // 最大值在左侧
} else {
left = mid; // 最大值在右侧（含 mid 自身）
}
}
return nums[right]; // left == right，即最大值
}
特殊情况（旋转 n 次）： [11, 13, 15, 17] 中 nums[mid] 始终 > nums[left]，一直 left = mid 向右收缩，最终指向最后一个元素 17。
变式二：允许重复元素 — LeetCode 154
LeetCode 154 — 寻找旋转排序数组中的最小值 II (Hard)
与 153 的唯一区别：数组中可能存在重复元素。
为什么简单改法行不通
初看似乎加一个相等分支即可——当 nums[mid] == nums[right] 时，沿用 right = mid（"往左搜索，不变"）：
// ❌ 错误写法
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid; // 包含 nums[mid] == nums[right] 的情况
}
这个写法在无重复元素时完全正确，但一旦有重复元素就会出错。 考虑反例：
nums = [3, 3, 1, 3]（旋转自 [1, 3, 3, 3]）：
| 步骤 | left | right | mid | nums[mid] | nums[right] | 判断 | 操作 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 3 | 1 | 3 | 3 | 3 == 3 | right = 1 |
| 2 | 0 | 1 | 0 | 3 | 3 | 3 == 3 | right = 0 |
最终 left == right == 0，nums[0] = 3，但正确答案是 1。错了。
问题根源：当 nums[mid] == nums[right] 时，mid 和 right 的值相同，我们无法判断 mid 落在左边子数组还是右边子数组：
- 在
[3, 3, 1, 3]中，mid=1 的值 3 来自左边子数组，最小值在 mid 右侧 - 在
[1, 3, 3, 3]中（旋转 n 次），mid=1 的值 3 来自右边子数组，最小值在 mid 左侧
两种完全相反的走向，无法仅凭值相等来判定。
正确解法
当 nums[mid] == nums[right] 时，我们无法判断方向，但可以利用重复元素的特点：即使 nums[right] 是最小值，数组中还存在一个与它相等的副本。因此可以把 right 安全地左移一位：
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2; // 防溢出写法
if (nums[mid] > nums[right]) {
left = mid + 1; // 最小值在右侧
} else if (nums[mid] < nums[right]) {
right = mid; // 最小值在左侧（含 mid）
} else {
right--; // 无法判断，安全左移
}
}
return nums[left];
}
right-- 为什么安全？ 假如 nums[right] 是唯一的最小值，right-- 就会把它丢掉。但此时 nums[mid] == nums[right]，说明 mid 处还有一个相同值作为"备份"，即使丢掉 right，最小值仍然留在 [left, mid] 区间内。
执行过程（仍是 [3, 3, 1, 3]）：
| 步骤 | left | right | mid | nums[mid] | nums[right] | 判断 | 操作 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 3 | 1 | 3 | 3 | 相等 | right = 2 |
| 2 | 0 | 2 | 1 | 3 | 1 | 3 > 1 | left = 2 |
| 3 | 2 | 2 | - | - | - | 退出 | 返回 nums[2] = 1 ✓ |
复杂度： 最坏情况（所有元素相同）退化为 O(n)，因为每次只能 right-- 移动一步；平均情况仍是 O(log n)。
寻找最大值 + 重复元素
对称处理：当 nums[mid] == nums[left] 时，left++（向右收缩），mid 处的副本保证最大值不会丢失。
int findMax(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2; // 向上取整
if (nums[mid] > nums[left]) {
left = mid; // 最大值在右侧（含 mid）
} else if (nums[mid] < nums[left]) {
right = mid - 1; // 最大值在左侧
} else {
left++; // 无法判断，安全右移
}
}
return nums[right];
}
对比总结
| 问题 | 比较对象 | mid 取整 | 缩小逻辑 | 重复元素处理 |
|---|---|---|---|---|
| 找最小值 | nums[right] |
向下 (l+r)/2 |
mid > right → l = mid+1；否则 r = mid |
mid == right → right-- |
| 找最大值 | nums[left] |
向上 (l+r+1)/2 |
mid < left → r = mid-1；否则 l = mid |
mid == left → left++ |
记忆技巧：
- 找谁就看那边：找最小值参照 right（右侧是较小的子数组），找最大值参照 left（左侧是较大的子数组）
- 出现
left = mid→ mid 向上取整；只出现right = mid→ mid 向下取整即可 - 重复相等时，向参照物方向收缩一位：和 right 比 →
right--；和 left 比 →left++