搜索旋转排序数组 II
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
已知存在一个按非降序排列的整数数组 nums，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]。
给你 旋转后 的数组 nums 和一个整数 target，请你判断 target 是否存在于数组中：存在返回 true，否则返回 false。请尽可能减少操作步骤。
示例 1
0 在数组中出现。示例 2
模拟答题者思考
1. 暴力：从左到右扫一遍看有没有 target，O(n)——能判断存在性，但题目希望尽量快，且与旋转有序结构无关。
2. 重复在哪里？和 #33 一样，旋转后任意 mid 至少有一半仍是原数组的非降序段；可以在那一半上用二分思想缩区间。但本题允许重复，nums[l] == nums[mid] == nums[r] 时无法区分「左半有序」还是「右半有序」。
3. 关键转化：先处理三端相等——同时 l++、r--，去掉两个与 mid 同值的端点（它们不可能单独成为唯一答案的判据）。其余情况照 #33：判哪半非降序，再看 target 是否落在该半的数值范围内。
4. 例 [2,5,6,0,0,1,2], target=0：二分过程中会在右半非降序段 [0,0,1,2] 内命中；若遇到 [1,0,1,1,1], target=0 这类重复密集区间，三端相等分支会线性挤边界，最坏 O(n)。
5. 返回布尔值：找到任意一个 nums[mid]==target 即可 true，无需记录下标；搜完区间仍无则 false。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
l, r | int | 定义：当前待搜索区间的左右边界 维护：若 target 存在，至少有一个下标落在 [l, r] 内更新：正常二分缩半；或在「三端相等」歧义时同步 l += 1、r -= 1 挤掉无法判定的重复值 |
mid | int | 定义：区间中点 (l + r) // 2维护：将区间切成左段 [l, mid] 与右段 [mid+1, r]；在非歧义时至少一段仍为非降序更新：每轮重算； nums[mid] == target 时立即返回 true |
歧义收缩 | — | 定义：当 nums[l] == nums[mid] == nums[r] 时，无法判断哪一半仍保持原非降序维护：此时不能安全地丢掉任一半区间，只能排除端点重复值 更新： l += 1 且 r -= 1 后 continue，进入下一轮 |
有序半段判定 | bool | 定义：若 nums[l] <= nums[mid]，认为左半 [l, mid] 非降序；否则右半 [mid+1, r] 非降序维护：与 #33 相同，但相等元素会使「严格升序」退化为「非降序」，边界比较用 <=更新：在有序半段上用 nums[l] <= target < nums[mid] 或 nums[mid] < target <= nums[r] 决定缩哪边 |
落码步骤
1. l = 0，r = len(nums) - 1
2. 当 l <= r：取 mid，若 nums[mid] == target 返回 true
3. 若 nums[l] == nums[mid] == nums[r]：l += 1，r -= 1，继续下一轮
4. 若 nums[l] <= nums[mid]（左半非降序）：nums[l] <= target < nums[mid] 则 r = mid - 1，否则 l = mid + 1
5. 否则（右半非降序）：nums[mid] < target <= nums[r] 则 l = mid + 1，否则 r = mid - 1
6. 循环结束返回 false
代码实现
class Solution:
def search(self, nums: list[int], target: int) -> bool:
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return True
if nums[l] == nums[mid] == nums[r]:
l += 1
r -= 1
continue
if nums[l] <= nums[mid]: # 左半 [l, mid] 非降序
if nums[l] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
else: # 右半 [mid+1, r] 非降序
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
return Falseclass Solution {
public:
bool search(vector<int>& nums, int target) {
int l = 0, r = (int)nums.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) return true;
if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
l++;
r--;
continue;
}
if (nums[l] <= nums[mid]) { // 左半 [l, mid] 非降序
if (nums[l] <= target && target < nums[mid])
r = mid - 1;
else
l = mid + 1;
} else { // 右半 [mid+1, r] 非降序
if (nums[mid] < target && target <= nums[r])
l = mid + 1;
else
r = mid - 1;
}
}
return false;
}
};
// 均摊 O(log n)，重复极多时最坏 O(n)；空间 O(1)复杂度分析
O(log n) 均摊，最坏 O(n)
O(1)
常见坑
漏掉三端相等分支：直接套 #33 会在 nums[l]==nums[mid]==nums[r] 时误判有序半段，可能错误缩区间导致漏答。
本题是非降序而非严格升序，左半有序时仍用 target < nums[mid]（不能写成 <=），因为 nums[mid]==target 已在前面返回。
返回值是布尔型：未找到应返回 false，不要返回 -1；找到一处即可 true，无需继续搜其他重复位置。
必测边界 Case
nums = [1], target = 1 → true
nums = [2,2,2,2], target = 2 → true（大量三端相等，靠缩边界与命中 mid）
nums = [2,5,6,0,0,1,2], target = 0 → true
nums = [1,0,1,1,1], target = 0 → true（需三端相等时 l++/r-- 才能继续二分）