Python二分查找出现RecursionError递归深度超限问题求助

问题根源 #

你的代码同时混用了迭代（while循环）和递归逻辑，这直接导致了RecursionError：

• 每次递归调用binarysearch(a,x)时，都会重新将low设为0、high设为数组末尾索引，相当于每次递归都从头开始查找，永远无法缩小查找范围，最终触发Python的递归深度上限。
• 代码中的exit()语句完全多余，return已经会终止函数执行。

修正方案 #

方案1：纯递归实现二分查找 #

import math

def binarysearch(a, x, low=0, high=None):
    # 仅首次调用时初始化high
    if high is None:
        high = len(a) - 1
    
    # 查找范围失效，返回未找到
    if low > high:
        return "Number not found"
    
    mid = math.ceil((low + high) / 2)
    if x == a[mid]:
        return mid
    elif x < a[mid]:
        # 递归查找左半区间，传入更新后的边界
        return binarysearch(a, x, low, mid - 1)
    else:
        # 递归查找右半区间，传入更新后的边界
        return binarysearch(a, x, mid + 1, high)

# 测试
a = [10,20,30,40,50]
x = 30
print(binarysearch(a, x))  # 输出: 2

方案2：纯迭代实现二分查找（无递归深度限制，更高效） #

import math

def binarysearch(a, x):
    low = 0
    high = len(a) - 1
    
    while low <= high:
        mid = math.ceil((low + high) / 2)
        if x == a[mid]:
            return mid
        elif x < a[mid]:
            high = mid - 1
        else:
            low = mid + 1
    # 循环结束未找到目标
    return "Number not found"

# 测试
a = [10,20,30,40,50]
x = 30
print(binarysearch(a, x))  # 输出: 2

关键修正点 #

• 递归实现时，必须将low和high作为参数传递，每次递归更新边界值，而非重新初始化。
• 移除所有多余的exit()语句，return已足够终止函数。
• 选择递归或迭代其中一种逻辑实现，避免混用两种方式导致逻辑混乱。

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