本文详解二分查找中 low/high 参数误用为元素值而非索引所导致的 IndexError 和运行时暴增的根本原因，并提供正确、高效、可复用的实现方案。
本文详解二分查找中 `low`/`high` 参数误用为元素值而非索引所导致的 `indexerror` 和运行时暴增的根本原因，并提供正确、高效、可复用的实现方案。
二分查找（Binary Search）是一种经典的 O(log n) 时间复杂度算法，但其正确性高度依赖于对搜索范围边界的正确定义。在原始代码中，核心错误在于将 low 和 high 错误地初始化为列表的元素值（如 list[0] 和 list[-1]），而非合法索引位置：
if low is None:
low = list[0] # ❌ 错误：list[0] 是元素（如 -287），不是索引！
if high is None:
high = list[-1] # ❌ 错误：list[-1] 是元素（如 293），不是索引！当列表元素绝对值较大（例如 ±300）时，midpoint = (low + high) // 2 会得到一个远超列表长度的数值（如 293 + (-287) // 2 ≈ 3 —— 表面看似安全，但一旦 low/high 均为大正数，如 500 和 800，midpoint 就可能达到 650）。此时 list[midpoint] 必然触发 IndexError: list index out of range。
更严重的是，后续“修复”——将 if list[midpoint] == target: 替换为 if midpoint == target: —— 实际上彻底破坏了算法语义：此时比较的是索引值和目标值，而非列表中该索引处的值。这导致逻辑完全错乱：即使 midpoint 碰巧等于 target（例如查找数字 5 时 midpoint 恰好为 5），也纯属巧合；而递归分支仍按原逻辑更新 low/high，造成搜索范围失控、重复计算、时间复杂度退化为 O(n) 甚至更高，因此实测耗时异常升高（如从纳秒级升至毫秒级）。
✅ 正确做法是：low 和 high 始终代表索引下标，初始值应为 0 和 len(list) - 1：
import random
import time
def binary_search(arr, target, low=None, high=None):
# ✅ 使用 arr 替代 list，避免覆盖内置类型
if low is None:
low = 0 # ✅ 索引起点：第一个元素位置
if high is None:
high = len(arr) - 1 # ✅ 索引终点：最后一个元素位置
# 边界检查：搜索区间无效
if low > high:
return -1 # ✅ 返回 -1 表示未找到，比 print 更符合函数职责
midpoint = (low + high) // 2
# ✅ 正确比较：目标值 vs 中间位置的元素值
if arr[midpoint] == target:
return midpoint
elif target < arr[midpoint]:
return binary_search(arr, target, low, midpoint - 1)
else:
return binary_search(arr, target, midpoint + 1, high)
# 性能测试
if __name__ == '__main__':
length = 100
sorted_list = set()
while len(sorted_list) < length:
sorted_list.add(random.randint(-3 * length, 3 * length))
sorted_list = sorted(list(sorted_list))
start = time.time()
for target in sorted_list:
assert binary_search(sorted_list, target) != -1 # 验证正确性
end = time.time()
avg_time = (end - start) / length
print(f"Binary search average time: {avg_time:.2e} seconds") # 示例输出：~1e-07 s关键注意事项总结：
- ? 命名规范：避免使用 list 作为参数名，它会遮蔽 Python 内置 list 类型，降低代码可读性与安全性；推荐使用 arr 或 sorted_arr。
- ? 返回设计：函数应返回结果（索引或 -1），而非 print()；调用方负责输出，符合单一职责原则。
- ? 边界条件：if low > high 是标准终止条件（注意不是 high < low，虽等价但前者更常见）；确保 midpoint 始终在 [low, high] 范围内计算。
- ? 性能验证：对 100 元素有序列表，单次搜索应在 100 纳秒量级（即 1e-7 秒），若实测达毫秒级（1e-3），必存在逻辑错误或非二分行为。
遵循以上修正，你的二分查找将严格保持 O(log n) 复杂度，稳定、可靠、高效——这才是算法本应展现的力量。
