递归实现Binary Search时出现最大递归深度超出错误的原因

你的代码存在几个关键问题，导致递归深度超限和结果错误：

• 空数组判断逻辑顺序错误：先计算mid再判断数组是否为空，当数组为空时会触发索引越界错误
• 每次递归都切片生成新数组，不仅浪费内存，还会让递归次数随数组规模增大而增加，容易触发Python的最大递归深度限制
• 返回的mid是子数组的索引，不是原数组中目标元素的真实位置

修正后的实现 #

用左右指针（low和high）代替数组切片，直接在原数组上操作，同时传递当前搜索范围的边界：

def BinarySearchRec(tab, x, low=0, high=None):
    # 初始化high为数组最后一个元素的索引
    if high is None:
        high = len(tab) - 1
    
    # 搜索范围为空，返回False表示未找到
    if low > high:
        return False
    
    # 计算当前范围的中间索引
    mid = (low + high) // 2
    
    if tab[mid] > x:
        # 目标在左半部分，缩小high到mid-1
        return BinarySearchRec(tab, x, low, mid - 1)
    elif tab[mid] < x:
        # 目标在右半部分，增大low到mid+1
        return BinarySearchRec(tab, x, mid + 1, high)
    else:
        # 找到目标，返回原数组的索引
        return mid

关键改进点 #

• 递归时仅传递索引边界，不生成新数组，大幅减少内存开销和递归调用的额外成本
• 递归次数严格控制为log2(n)级别，远低于Python默认的递归深度限制（默认1000），避免超限问题
• 返回的是原数组中目标元素的真实索引，结果准确
• 先判断搜索范围是否为空，避免索引越界错误

内容的提问来源于stack exchange，提问作者Blem.Hamza