搜索旋转排序数组 II

下面 15 步动画会按主解代码推进，而不是泛泛讲题型。

1. 看输入：数组 [1,0,1,1,1] 是旋转后还带重复值的有序数组，要判断 target=0 是否存在，返回 true/false。

2. 初始化双指针：l 指向下标 0，r 指向下标 4，搜索窗口 [0,4] 覆盖整个数组；while l 小于等于 r 时反复二分。

3. 第一轮·取中点：窗口 [0,4] 取中点 mid=2，nums[mid]=1。

4. 第一轮·比中点与目标：nums[mid]=1 不等于 target=0，没命中，继续判断该往哪半收缩。

5. 第一轮·三端是否相等：nums[l]、nums[mid]、nums[r] 都是 1，重复值把哪半有序的信息盖住了，无法二分。

6. 第一轮·两端各收一格：三端相等时只能保守地各收一格：l 变 1、r 变 3，排除两端下标 0 和 4，窗口收成 [1,3]。

7. 第二轮·取中点：回到循环，窗口 [1,3] 取中点 mid=2，nums[mid]=1。

8. 第二轮·比中点与目标：nums[mid]=1 仍不等于 target=0，继续判断有序半边。

9. 第二轮·左半是否有序：这轮三端不全等。nums[l]=0 小于等于 nums[mid]=1，说明左半段下标 [1,2] 是有序升序的。

10. 第二轮·目标落在左半：target=0 满足 nums[l]=0 小于等于 0 且 0 小于 nums[mid]=1，落在有序左半，丢掉 mid 及右边：r=mid-1=1，窗口收成 [1,1]。

11. 第三轮·取中点：窗口只剩 [1,1]，取中点 mid=1，nums[mid]=0。

12. 第三轮·命中目标：nums[mid]=0 等于 target=0，在下标 1 处找到目标，标绿命中。

13. 返回结果：目标存在，函数返回 true。若循环结束 l 越过 r 仍没命中，则会返回 false。

14. 不变量：窗口只缩不放：三轮里窗口 [0,4]→[1,3]→[1,1] 单调收缩：有序半边能砍一半，三端相等只能各收一格，所以最坏会退化到逐格扫。

15. 复杂度直觉：无重复时每轮砍半是 O(log n)；像 [1,1,1,...] 这种全相等会反复走 l++、r--，最坏退化到 O(n)，只用常数额外空间。

记住这题的代码骨架：题意约束先落到状态变量，再用循环或递归维护它。