题目重点：黑盒回答输入集合是否不包含完整坏对，跨两半时分别定位端点。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- items身份唯一，恰有一对不同元素隐藏；is_clean(S)=True当且仅当S不同时包含两端。
- 本文采用恰一坏对合同；求所有坏对是另一变体，不能反复移掉一端后就称找到全部。黑盒允许传任意子集。
解题路线
- 把候选分L/R，若L不clean则两端都在L；否则若R不clean则在R；否则必为一端在L、一端在R。
- 跨半时用整R作保证存在的一端集合，检查L的一半+R：不clean就选该半，否则选另一半，最终找到u。然后以[u]与R的一半查找v。
- 每次减半，逻辑查询O(logn)。但子集长度可很大；若构造/黑盒扫描按元素收费，调用数少不等于总时间O(logn)，尤其跨半定位时反复复制整R。
手动走一遍
[a,b,c,d]坏对(a,d)：L[a,b]和R[c,d]各clean，查[a]+R不clean定位a，再查[a,c]clean定位d。坏对(a,b)时首次L不clean，直接缩到L返回两端。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def find_pair(items,is_clean):
items=list(items)
if len(items)<2 or is_clean(items):
raise ValueError("exactly one hidden bad pair required")
current=items
while len(current)>2:
mid=len(current)//2
left,right=current[:mid],current[mid:]
if not is_clean(left):
current=left
elif not is_clean(right):
current=right
else:
# One endpoint is in each half.
while len(left)>1:
mid=len(left)//2
x,y=left[:mid],left[mid:]
left=x if not is_clean(x+right) else y
u=left[0]
while len(right)>1:
mid=len(right)//2
x,y=right[:mid],right[mid:]
right=x if not is_clean([u]+x) else y
return u,right[0]
return tuple(current)
复杂度
黑盒调用O(logn)；当前list复制及黑盒若线性扫描，最坏O(nlogn)累计元素量，工作内存O(n)。若支持持久子集视图可减少构造，但oracle自己的成本仍独立计。
易错点与追问
容易失分的边界
- True/False语义反过来会使全部二分分支错。
- 多个坏对时“两个半边均clean”不保证跨半只有一个端点组合，不能套单对证明。
继续深挖
- 若有多个坏对，怎样用递归拆集合与跨集查询枚举所有边？
- oracle只接受固定大小批次，如何改变可辨识性与查询策略？
