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

Question

所以我正在用Python写一个递归的二进制搜索算法，它工作得很好。。。。。。除非我试过某个号码。你知道吗

我正在整理一个由10000个随机数字组成的列表，这些数字已经被排序了。你知道吗

它最终会失败，并出现以下错误：

RecursionError: maximum recursion depth exceeded while calling a Python object

我在函数中加入了计数器来跟踪低点/高点和当前搜索计数。当我运行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，直到它达到诅咒的上限。你知道吗

我的职责是：

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

原因是你没有处理一个终止条件。当您的下限高于上限时，这意味着您正在搜索的元素不在列表中，您应该在那里返回-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