旋转排序数组有重复元素时，二分查找为什么会退化？
简化版
旋转排序数组没有重复元素时，可以通过比较 nums[left]、nums[mid]、nums[right] 判断哪一半有序。
但有重复元素时，可能出现 nums[left] == nums[mid] == nums[right]，这时无法判断哪边有序，只能收缩边界，例如 left++、right--。因此最坏情况下会退化到 O(n)。
重复元素会破坏二分每次排除一半的能力。
详细版
无重复旋转数组中：
nums[left] <= nums[mid]通常说明左半边有序。
但有重复时：
[1, 0, 1, 1, 1]left、mid、right 可能都等于 1，此时无法确定旋转点在哪一边。
处理方式：
if nums[left] == nums[mid] && nums[mid] == nums[right]:
left++
right--这种保守收缩只排除少量元素，所以最坏复杂度是 O(n)。
完整版教学
1. 无重复旋转数组为什么能二分
旋转排序数组由两个有序段拼接而成。
没有重复元素时，比较 nums[left] 和 nums[mid]，通常能判断左半边是否有序。
if nums[left] <= nums[mid]:
左半边有序
else:
右半边有序然后再判断 target 是否落在有序半边范围内，从而排除另一半。
2. 重复元素带来什么问题
重复元素会让比较信息变少。
例如：
[1, 1, 1, 0, 1]当 nums[left] == nums[mid] == nums[right] 时，你无法通过这些值判断最小值或旋转点到底在左边还是右边。
二分依赖“比较结果能排除一半”，重复元素会让比较结果失去区分度。
3. 为什么只能收缩边界
当三者相等时，left 和 right 上的值都等于 mid。
如果它们不是 target，就可以安全跳过；如果它们是 target，查找题已经可以返回 true。
常见写法：
if nums[left] == nums[mid] && nums[mid] == nums[right]:
left++
right--这是一种保守处理，保证不漏答案。
4. 正常情况下怎么判断有序半边
如果没有三者相等的模糊情况，仍然可以判断：
if nums[left] <= nums[mid]:
左半边有序
else:
右半边有序然后检查 target 是否在有序半边。
左半有序时：
nums[left] <= target < nums[mid]如果成立，搜索左半；否则搜索右半。
5. 为什么最坏是 O(n)
考虑数组：
[1, 1, 1, 1, 1, 1, 1]或者只有一个不同值被重复值包围。
每次都可能只能执行：
left++
right--这样无法保证每轮砍半，最坏就退化为线性扫描。
6. 和寻找最小值有什么关系
旋转数组查找 target 和寻找最小值都有类似问题。
当：
nums[mid] == nums[right]时，无法判断最小值在左还是右，常见做法是：
right--同样会导致最坏 O(n)。
7. 面试怎么讲清楚
可以按这个顺序回答：
| 步骤 | 内容 |
|---|---|
| 先说明无重复能二分 | 至少一边有序 |
| 再说明重复的模糊情况 | 三点相等无法判断 |
| 给出保守收缩 | left++、right-- |
| 最后说明复杂度 | 平均较好，最坏 O(n) |
这样面试官会觉得你知道为什么退化，而不是只会背代码。
8. 常见误区与追问
- 误区：旋转数组二分一定是
O(log n)。 有重复元素时最坏会退化到O(n)。 - 误区：
nums[left] <= nums[mid]总能说明左边有序。 重复元素下可能信息不足，尤其三点相等时。 - 误区：遇到相等可以随便丢一半。 不能随便丢，可能漏掉旋转点或 target。
- 追问：为什么
right--是安全的？ 在模糊且未命中 target 时，右端重复值不提供额外信息，可以保守丢弃。 - 追问：有没有办法保证
O(log n)？ 对任意重复输入无法保证，因为比较信息可能不足。