Python中的遞歸二分法搜索命中遞歸天花板

Question

因此，我正在Python中編寫一個遞歸二分搜索算法，它一直工作的很好......除了當我嘗試一定數量時。

我正在處理已經排序的10,000個隨機數字的列表。

它最終失敗，此錯誤：

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，直到它到達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

的原因是你沒有處理一個終止條件。當你的下限高於你的上限時，這意味着你正在搜索的元素不在列表中，你應該在那裏返回-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