本文深入剖析递归实现二分查找时因缺失基础终止条件和错误切片导致的 IndexError，给出正确、健壮的递归版本，并指出性能更优的索引传递式改进方向。
本文深入剖析递归实现二分查找时因缺失基础终止条件和错误切片导致的 `indexerror`，给出正确、健壮的递归版本，并指出性能更优的索引传递式改进方向。
二分查找（Binary Search）要求输入数组有序，且必须在每次递归调用前明确处理「搜索区间为空」这一边界情况。原代码中 binarySearch2 在未检查 arr 长度的情况下直接计算 right = len(arr) - 1 和 mid = (left + right) // 2，当递归传入空列表 [] 时，len(arr) == 0 → right == -1 → mid == -1，随后执行 arr[mid]（即 arr[-1]）将触发 IndexError: list index out of range。
更根本的问题在于逻辑缺陷与切片错误并存：
- ❌ 错误切片：arr[:mid - 1] 实际截取的是 [0 : mid-1)，比预期少一个元素（应为 arr[:mid]）；
- ❌ 缺失终止条件：未在函数入口处判断 if len(arr) == 0: return False；
- ❌ 重复排序：每次递归都调用 arr.sort()，既低效又破坏原始数据结构（尤其当传入已排序子列表时，.sort() 可能改变其顺序或引发异常）。
以下是修复后的正确递归实现（保留切片风格，便于理解）：
def binarySearch2(arr, val):
# 预排序仅执行一次，避免递归中重复调用
arr = sorted(arr) # 使用 sorted() 返回新列表，不修改原输入
def search(sub_arr):
# ✅ 关键：递归终止条件——空数组直接返回 False
if len(sub_arr) == 0:
return False
left = 0
right = len(sub_arr) - 1
mid = (left + right) // 2
if val == sub_arr[mid]:
return True
elif val > sub_arr[mid]:
# ✅ 正确切片：右半部分为 sub_arr[mid+1:]
return search(sub_arr[mid + 1:])
else: # val < sub_arr[mid]
# ✅ 正确切片：左半部分为 sub_arr[:mid]（不含 mid）
return search(sub_arr[:mid])
return search(arr)✅ 验证示例：
for i in range(10):
print(f"search {i}: {binarySearch2([1, 2, 3, 4, 5, 6, 7, 8, 9], i)}")
# 输出：search 0: False, search 1: True, ..., search 9: True, search 10: False⚠️ 注意事项：
- 切片递归虽直观，但每次创建新子列表带来 O(n) 空间开销（总时间复杂度仍为 O(log n)，但常数因子大）；
- 生产环境中推荐索引传递式递归（不切片），仅维护 left/right 下标，空间复杂度降至 O(log n)（仅递归栈），且避免内存拷贝：
def binarySearch_optimized(arr, val):
arr = sorted(arr) # 仅初始化时排序一次
def search(left, right):
if left > right: # ✅ 更精准的终止条件：区间无效
return False
mid = (left + right) // 2
if val == arr[mid]:
return True
elif val > arr[mid]:
return search(mid + 1, right)
else:
return search(left, mid - 1)
return search(0, len(arr) - 1)? 总结：
递归二分查找的健壮性依赖于两点：严格的终止条件（空区间/越界区间判断） 和 语义正确的区间划分（切片或索引）。忽略任一者都将导致运行时错误或逻辑错误。优先采用索引传递方式，在保证正确性的同时兼顾性能与内存效率。
