Python 中的递归二进制搜索达到递归上限

Question

所以我在 Python 中编写了一个递归二进制搜索算法并且它一直工作得很好......除了我尝试了某个数字。

我正在处理一个包含 10,000 个已排序随机数的列表。

最终失败并出现此错误：

RecursionError: maximum recursion depth exceeded while calling a Python object

我在函数中放入了计数器来跟踪 low/high 点和当前搜索计数。当我 运行 bSearch(3333) 时，我得到上述错误和这个奇怪的输出...

0 None 1
0 4998 2
0 2498 3
0 1248 4
0 623 5
312 623 6
312 466 7
312 388 8
312 349 9
331 349 10
331 339 11
336 339 12
338 339 13
338 337 14
338 337 15

它一直重复 338 337，直到达到 cursions 上限。

这是我的函数：

def bSearch(list, value, lowPoint=0, highPoint=None, searchNum=1):
    print(lowPoint,highPoint,searchNum)
    searchNum += 1
    if highPoint is None:
        highPoint = len(list) - 1
    if lowPoint == highPoint:
        if list[lowPoint] == value:
            return lowPoint, searchNum
        else:
            return -1, searchNum
    midPoint = (lowPoint + highPoint) // 2
    if list[midPoint] > value:
        return bSearch(list, value, lowPoint, midPoint - 1, searchNum)
    elif list[midPoint] < value:
        return bSearch(list, value, midPoint + 1, highPoint, searchNum)
    else:
        return midPoint

Answer 1

原因是您没有处理一个终止条件。当您的下限高于上限时，这意味着您要搜索的元素不在列表中，您应该 return a -1 在那里。

def bSearch(list, value, lowPoint=0, highPoint=None, searchNum=1):
    print(lowPoint,highPoint,searchNum)
    searchNum += 1
    if highPoint is None:
        highPoint = len(list) - 1
    if lowPoint == highPoint:
        if list[lowPoint] == value:
            return lowPoint, searchNum
        else:
            return -1, searchNum
    if lowPoint > highPoint:
        return -1,searchNum
    midPoint = (lowPoint + highPoint) // 2
    if list[midPoint] > value:
        return bSearch(list, value, lowPoint, midPoint - 1, searchNum)
    elif list[midPoint] < value:
        return bSearch(list, value, midPoint + 1, highPoint, searchNum)
    else:
        return midPoint