0
因此,我正在Python中編寫一個遞歸二分搜索算法,它一直工作的很好......除了當我嘗試一定數量時。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
-__- 應該通過更多的想到的終止條件! 謝謝! – Zeratas
我也只是像這樣組合了兩個: if lowPoint> = highPoint: – Zeratas
是的,這是有道理的\ m / – gman