Python递归式列表二分搜索触发最大递归深度，求问题原因

我来帮你排查问题！你的递归版二分搜索代码有两个关键bug，直接导致了最大递归深度错误，咱们一个个说：

1. 终止条件的顺序完全搞反了 #

你现在是先算中间索引middle，再判断right < left（也就是没有元素可搜的终止条件）。这会导致什么问题？当搜索范围已经不存在时（比如right=2，left=3），你还是会硬着头皮计算middle，甚至去访问alist[middle]，不仅可能触发索引越界，更致命的是，这个本该终止递归的条件没提前生效，导致递归停不下来。

正确的逻辑应该是先检查有没有搜索范围，没有就直接返回-1终止递归，再去做后续的计算和比较。

2. right参数的初始化逻辑有坑 #

你用了right = right or len(alist) - 1来初始化，这个写法在第一次调用时没问题，但递归调用时就炸了。比如当你要搜索左半部分，传入right=0时，因为0在Python里是假值，or会直接返回len(alist)-1，相当于把搜索范围又拉回了整个列表，递归根本收不住，直接无限循环直到触发深度上限。

正确的初始化应该是只在第一次调用（也就是right为默认的None时）才设置为列表长度-1，其他时候保持传入的参数不变。

修复后的完整代码 #

def binary_search(alist, x, left=0, right=None):
    # 仅在第一次调用时初始化right，避免覆盖递归传入的合法值
    if right is None:
        right = len(alist) - 1
    
    # 先判断终止条件：无搜索范围直接返回-1
    if right < left:
        return -1
    
    middle = left + (right - left) // 2
    if x == alist[middle]:
        return middle
    elif x < alist[middle]:
        return binary_search(alist, x, left, middle - 1)
    else:  # 剩下的情况就是x大于中间元素
        return binary_search(alist, x, middle + 1, right)

if __name__ == '__main__':
    test_list = [1, 3, 5, 7, 9, 11]
    print(binary_search(test_list, 7))  # 输出3，正确找到目标
    print(binary_search(test_list, 2))  # 输出-1，目标不存在

验证一下 #

用上面的测试列表运行，不管是找存在的元素还是不存在的元素，都能正常返回结果，不会再触发递归深度超限的问题啦。

内容的提问来源于stack exchange，提问作者Reza Afra