§1

题目描述

nums 原本升序，被在某个下标处旋转过（如 [0,1,1,1] → [1,1,1,0]），数组可能含重复元素。给定 target，存在返回 true，否则返回 false。

输入 = nums = [1,1,1,0,1], target = 0　输出 = true（0 在下标 3）

§2

思路解析

一句话答案：LeetCode 81 搜索旋转排序数组 II：在旋转过又带重复值的升序数组里判断 target 在不在，用旋转二分找它，但重复值让「哪半有序」失灵——三数相等时左右各缩一格去重，平均 O(log n)、最坏退化 O(n)。

数组被旋转过又带重复，只判 target 在不在

nums 本是升序，从某处切开对调，比如 [0,1,1,1] 变 [1,1,1,0]，还可能有重复数字。给定 target，在就返回 true、否则 false，只判在不在。题面 nums=[1,1,1,0,1]、target=0 为 true。

扫一遍能过，可为什么不甘心停在 O(n)

把 target 和每个数挨个比，n 个数最坏比满 n 次，是 O(n)。数据小也能过，但数组是升序旋转来的、自带秩序没用上；升序本可二分 O(log n) 定位，题目旋转又掺重复，就是逼你捡回二分。

凭什么还能二分，重复又是怎么搅局的

旋转后数组不再整体有序，却是两段各自升序的拼接。以中点 mid 为界，nums[l]≤nums[mid] 就说明左半升序，否则拐点在左半、右半才升序；锁定有序那半看 target 在不在它的范围里，在就进这半、不在去另一半，一样砍掉一半。

麻烦全在重复：nums[l]=nums[mid] 时左半可能有序也可能不是，光看分不清；尤其三者全相等，大小比较彻底失去区分力，哪半有序都判不了。

三个数一样时，指针到底该往哪挪

每轮取中点 mid=(l+r)//2，nums[mid]==target 就返回 true。没中分三支：三者 nums[l]、nums[mid]、nums[r] 相等时判不出哪半有序，只能 l 加一、r 减一各缩一格，最坏退化就埋在这；nums[l]≤nums[mid] 时左半有序，nums[l]≤target<nums[mid] 收左 r=mid-1、否则 l=mid+1；否则右半有序，nums[mid]<target≤nums[r] 收右 l=mid+1、否则 r=mid-1。开闭对齐有序方向，写反等号就把 target 推错半边。

拿 [1,1,1,0,1] 找 0，三轮各发生什么

起手 l=0、r=4。第一轮 mid=(0+4)//2=2，nums[2]=1 不是 0；nums[0]、nums[2]、nums[4] 全是 1，三者相等，各缩一格，l 到 1、r 到 3。

第二轮 l=1、r=3，mid=2，nums[2]=1 不是 0；nums[l]=nums[mid]=1 但 nums[r]=nums[3]=0，不触发三者相等，nums[l]≤nums[mid] 判左半有序，1≤0<1 不成立故 target 靠右，l=mid+1=3。第三轮 l=r=3，mid=3，nums[3]=0 命中返回 true。首轮靠缩一格跨过重复区，后两轮才是常规二分。

少了缩一格这一支，重复数组会怎么判错

砍半时是 O(log n)、空间 O(1)；但 [1,1,1,1,1] 找 0 这种几乎全相等的数组，每轮都撞三者相等只能缩一格，退化成 O(n)。

照搬 33 题漏掉 nums[l]==nums[mid]==nums[r] 这支，重复数组哪半有序会判错、区间收不动死循环。相等时只动一边、l++ 忘了 r--，某些分布下区间收不干净会漏看 target，两端得同时缩。开闭的等号也别写反，左半该 <、右半该 ≤，站错边 target 就判到另一半。

▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开

三件事：先看中点中没中；没中就找出有序的那一半；有序半里用大小关系决定往左还是往右缩。三者相等是特例，左右各缩一格。

左指针 l 指向下标 0，右指针 r 指向下标 13，搜索区间是整个数组。目标值 target = 0。

在区间 [0, 13] 里取中点 mid = (0+13)/2 = 6，这一格的值是 1。先拿它和目标 0 比。