为何我的Python二分查找出现RecursionError: 超出最大递归深度错误？

这个问题其实出在右半部分的搜索范围没有正确收敛，咱们一步步拆解来看：

原代码的问题点 #

先看你原来的递归右分支：

else:
    return bin_search(l,i,pos,end)

当目标元素比l[pos]大时，你把新的搜索范围设为[pos, end)，但这里忽略了两个关键：一是l[pos]已经被证明比目标小，完全可以排除；二是这个范围设置会直接导致无限递归循环。

举个具体的错误场景 #

假设你调用bin_search([1,3,5], 6, 0, 3)（这里end取列表长度，是左闭右开的区间）：

1. 第一次：start=0, end=3，pos=(0+3)//2=1，6>3，递归调用bin_search([1,3,5],6,1,3)
2. 第二次：start=1, end=3，pos=(1+3)//2=2，6>5，递归调用bin_search([1,3,5],6,2,3)
3. 第三次：start=2, end=3，pos=(2+3)//2=2，6>5，又递归调用bin_search([1,3,5],6,2,3)
4. 接下来就陷入了死循环：每次的start和end都是2和3，pos永远是2，递归永远不会触发start >= end的终止条件，直到Python的递归深度上限被触发，抛出RecursionError。

修改后的代码为什么能解决问题？ #

当你把右分支改成：

else:
    return bin_search(l,i,pos + 1,end)

相当于把搜索范围调整为[pos+1, end)，直接排除了已经确认不符合条件的l[pos]，范围会持续缩小：
还是用刚才的例子，第三次调用后会变成bin_search([1,3,5],6,3,3)，这时候start >= end，触发终止条件，返回False，递归正常结束。

补充：左分支为什么没问题？ #

你可能会好奇左分支return bin_search(l,i,start,pos)为什么没出错——因为左分支的场景是目标比l[pos]小，此时搜索范围设为[start, pos)是合理的：当start和pos相邻时，下一次递归的end等于start，会触发终止条件，不会无限循环。比如找0在[1,3,5]里，最后会走到start=0, end=0，返回False。

总结一下：二分查找的递归关键是每次递归都要严格缩小搜索范围，右分支必须排除pos位置的元素，否则会出现无法收敛的循环~

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