我正在對學校進行遞回二進制搜索。由于測驗代碼，我僅限于我的輸入lyst和target輸出應該只是一個bool斷言是否找到目標。我發現了其他類似我的問題的例子，但他們通常會求助于將上限和下限作為輸入的一部分。我顯然不能這樣做。我也不確定是否可以使用輔助功能。我會試著找出答案。這是我到目前為止所擁有的：
def binary_search(lyst, target):
left = 0
right = len(lyst) - 1
while left <= right:
mid = (right left) // 2
if len(lyst) == 0:
return False
elif lyst[mid] < target:
left = mid
return binary_search(lyst[left: right], target)
elif lyst[mid] > target:
right = mid
return binary_search(lyst[left: (right 1)], target)
elif lyst[mid] == target:
return True
return False
它適用于某些情況，但不是全部。例如，它會在以下串列中找到 3 的目標my_list = [1,2,3,4,5,6,7,8,9,10]，但不會在 1-15 的串列中找到 3。我覺得我很接近，但可以使用一點幫助。
uj5u.com熱心網友回復：
由于遞回不是必需的，您可以只跟蹤開始和結束索引并在它們擠在一起時停止。這避免了切片，同時還允許函式簽名保持不變：
def binary_search(lyst, target):
start = 0
end = len(lyst)
while start < end:
mid = (end - start) // 2 start
if lyst[mid] == target:
return True
if target < lyst[mid]:
end = mid
else:
start = mid 1
return False
my_list = [1,2,3,4,5,6,7,8,9,10, 11, 12, 13, 14, 15]
print(binary_search(my_list, 3))
# True
# Some edge cases:
print(binary_search([1], 3))
# False
print(binary_search([], 3))
# False
print(binary_search([3], 3))
# True
print(binary_search([1, 3], 3))
# True
如果您仍想對不需要回圈的切片使用遞回，則使用遞回代替。其他一切都非常相似，但在這種情況下，您需要處理遞回應該停止的邊緣情況：
def binary_search_rec(lyst, target):
if not lyst:
return False
mid = len(lyst) // 2
if lyst[mid] == target:
return True
if target < lyst[mid]:
return binary_search_rec(lyst[:mid], target)
else:
return binary_search_rec(lyst[mid 1:], target)
當然，正如評論中提到的那樣，您會降低效率，因為您需要在每次呼叫時創建新串列。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/507846.html