京公网安备11010502063487号第 33 题的进阶：数组同样是升序被旋转过，但这次允许有重复的元素。二分查找的关键是"每次总有一半是有序的"，可以据此判断目标在不在有序的那半边。重复元素会破坏这个判断：当 nums[lo]、nums[mid]、nums[hi] 三者都相等时，无法知道哪半边是有序的（例如 [1, 1, 1, 0, 1] 和 [1, 0, 1, 1, 1] 在这三个位置上看起来一样）。这时只能把区间两端各缩小一格，然后继续。本文用真实数据展示不处理这种情形的写法错在哪里，展示这个特殊处理带来的最坏情形退化，给出五种语言的实现，并把缩小区间的过程做成分步演示。
完整题目见官方页面（链接在文末）。只要求返回目标是否存在。基准解是最直接的 target in nums。一共 14 组用例，覆盖：官方两个示例、单个元素、全是同一个数、目标在重复段里、目标在旋转点旁边、无重复元素的情形：
输入 [[2,5,6,0,0,1,2],0] 输出 true 输入 [[2,5,6,0,0,1,2],3] 输出 false 输入 [[1],1] 输出 true 输入 [[1],0] 输出 false 输入 [[1,0,1,1,1],0] 输出 true 输入 [[1,1,1,0,1],0] 输出 true
把第 33 题的写法原样搬过来（nums[lo] <= nums[mid] 就认为左半有序），在有重复元素时会出错：nums[lo] == nums[mid] 并不能保证 [lo, mid] 有序，因为旋转点可能就在里面，被相同的值遮住了。下面是这种写法的真实结果，包括随机测试和穷举：
# 沿用第 33 题（元素互不相同）的写法，没有处理 nums[lo] == nums[mid] == nums[hi] [1, 0, 1, 1, 1], target=0: 沿用旧写法 -> False solve -> True [1, 1, 1, 0, 1], target=0: 沿用旧写法 -> True solve -> True [2, 2, 2, 3, 2, 2, 2], target=3: 沿用旧写法 -> True solve -> True [2, 5, 6, 0, 0, 1, 2], target=0: 沿用旧写法 -> True solve -> True 随机 30000 组：旧写法出错的有 9 组（0.03%） 穷举：所有长度 1 到 8、只含 0 和 1 的有序数组的所有旋转，目标取 0 或 1，共 7172 种（含重复的数组），旧写法出错 180 种；最短的一个反例：[0, 1, 0, 0, 0]，target=1
[1, 0, 1, 1, 1] 找 0，旧写法返回 False，正确答案是 True。有意思的是，在随机的 30000 组数据里，旧写法只出错了 9 组（0.03%），几乎测不出来；但穷举所有长度 1 到 8、只含 0 和 1 的有序数组的所有旋转、目标取 0 或 1（共 7172 种，含重复的数组），旧写法出错了 180 种（约 2.5%）。最短的反例是长度 5 的 [0, 1, 0, 0, 0] 找 1。所以这个错误在随机测试里很容易漏掉，因为它只在重复值恰好把旋转点遮住的特定排列上才出现。
在第 33 题的基础上，每一轮取中点后先检查是否命中；然后加一个特判：如果 nums[lo] == nums[mid] == nums[hi]，无法判断哪半边有序，就 lo++、hi-- 各缩一格（因为 mid 不等于目标，lo 和 hi 位置的值与 mid 相同，也不等于目标，可以放心丢掉）。其余情形与第 33 题一样：看 nums[lo] <= nums[mid] 判断左半是否有序，再判断目标是否落在有序的那一半里。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if nums[mid] == target: return True if nums[lo] == nums[mid] == nums[hi]: # 三者相等：分不清哪半边有序，只能把两端各缩一格 lo += 1 hi -= 1 elif nums[lo] <= nums[mid]: # 左半 [lo, mid] 有序 if nums[lo] <= target < nums[mid]: hi = mid - 1 else: lo = mid + 1 else: # 右半 [mid, hi] 有序 if nums[mid] < target <= nums[hi]: lo = mid + 1 else: hi = mid - 1 return False
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[2,5,6,0,0,1,2],0] → true [[2,5,6,0,0,1,2],3] → false [[1],1] → true [[1],0] → false [[1,0,1,1,1],0] → true [[1,1,1,0,1],0] → true
Java · 解法代码class Solution { public boolean search(int[] nums, int target) { int lo = 0, hi = nums.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] == target) return true; if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) { // 三者相等：分不清哪半边有序，只能把两端各缩一格 lo++; hi--; } else if (nums[lo] <= nums[mid]) { // 左半 [lo, mid] 有序 if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1; } else { // 右半 [mid, hi] 有序 if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1; } } return false; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[2,5,6,0,0,1,2],0] → true [[2,5,6,0,0,1,2],3] → false [[1],1] → true [[1],0] → false [[1,0,1,1,1],0] → true [[1,1,1,0,1],0] → true
Go · 解法代码func search(nums []int, target int) bool { lo, hi := 0, len(nums)-1 for lo <= hi { mid := lo + (hi-lo)/2 if nums[mid] == target { return true } if nums[lo] == nums[mid] && nums[mid] == nums[hi] { // 三者相等：分不清哪半边有序，只能把两端各缩一格 lo++ hi-- } else if nums[lo] <= nums[mid] { // 左半 [lo, mid] 有序 if nums[lo] <= target && target < nums[mid] { hi = mid - 1 } else { lo = mid + 1 } } else { // 右半 [mid, hi] 有序 if nums[mid] < target && target <= nums[hi] { lo = mid + 1 } else { hi = mid - 1 } } } return false }
$ go build -o bin . && ./bin < cases.jsonl [[2,5,6,0,0,1,2],0] → true [[2,5,6,0,0,1,2],3] → false [[1],1] → true [[1],0] → false [[1,0,1,1,1],0] → true [[1,1,1,0,1],0] → true
JavaScript · 解法代码function search(nums, target) { let lo = 0, hi = nums.length - 1; while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); if (nums[mid] === target) return true; if (nums[lo] === nums[mid] && nums[mid] === nums[hi]) { // 三者相等：分不清哪半边有序，只能把两端各缩一格 lo++; hi--; } else if (nums[lo] <= nums[mid]) { // 左半 [lo, mid] 有序 if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1; } else { // 右半 [mid, hi] 有序 if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1; } } return false; }
$ node run.js < cases.jsonl [[2,5,6,0,0,1,2],0] → true [[2,5,6,0,0,1,2],3] → false [[1],1] → true [[1],0] → false [[1,0,1,1,1],0] → true [[1,1,1,0,1],0] → true
C++ · 解法代码#include <vector> using namespace std; class Solution { public: bool search(vector<int>& nums, int target) { int lo = 0, hi = (int)nums.size() - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] == target) return true; if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) { // 三者相等：分不清哪半边有序，只能把两端各缩一格 lo++; hi--; } else if (nums[lo] <= nums[mid]) { // 左半 [lo, mid] 有序 if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1; } else { // 右半 [mid, hi] 有序 if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1; } } return false; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[2,5,6,0,0,1,2],0] → true [[2,5,6,0,0,1,2],3] → false [[1],1] → true [[1],0] → false [[1,0,1,1,1],0] → true [[1,1,1,0,1],0] → true
共 14 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 14/14 Java 通过 14/14 Go 通过 14/14 JavaScript 通过 14/14 C++ 通过 14/14
无重复元素时二分每次减半，是 O(log n)。但有重复时，如果数组几乎全是同一个数，每一轮都会走进"三者相等"的分支，区间只缩小 2，变成了 O(n)。下面是真实统计的循环次数：元素互不相同的旋转数组，对比几乎全是 1、中间只有一个 0 的数组（目标不存在）：
循环次数：无重复元素的旋转数组 vs 几乎全是同一个数（最坏情形，目标不存在） n= 1000: 元素互不相同 10 次 几乎全是 1 501 次 n= 100000: 元素互不相同 17 次 几乎全是 1 50001 次 n= 1000000: 元素互不相同 20 次 几乎全是 1 500001 次
元素互不相同时，n 从 1000 增加到 100 万，循环次数只从 10 次增加到 20 次；几乎全是同一个数时，循环次数是 501、50001、500001，正好是 n 的一半，因为每次缩 2。所以这道题在最坏情形下只是 O(n)，并不比线性扫描更好，这是重复元素带来的、无法回避的代价：三者相等时，确实没有任何信息可以用来丢掉一半。
Python 版本另外和 target in nums 做了随机对拍：长 1 到 10、取值 0 到 4（重复值很多）的有序数组随机旋转，target 取 -1 到 5：
随机对拍 30000 组（长 1 到 10、取值 0 到 4（重复值很多）的有序数组随机旋转，target 取 -1 到 5），solve 与 brute 的结果全部一致。
另外四种语言只在上面 14 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用 [1, 1, 1, 0, 1]（一个被旋转过的数组，旋转点在 0 那里）找 0。第一轮 mid = 2，三者都是 1，分不出哪半边有序，两端各缩一格；第二轮 nums[lo] ≤ nums[mid]，左半看起来有序，但目标 0 不在左半的范围里，去右半；下一轮直接命中。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。