我一直在嘗試遞歸地編寫二進制搜索。當我使用list [：]語法執行此操作時，由于出現幾個錯誤或沒有獲得正確的值，因此無法獲得預期的結果。def binary_search(arr, val): left = 0 right = len(arr)-1 mid = (left + right)//2 #Go through the array if (val == arr[mid]): return mid #Check right side of arr if (val > arr[mid]): return binary_search(arr[mid+1:], val) #Check left side of arr return binary_search(arr[:mid], val)編輯：示例輸入和輸出arr1 =[]for i in range(10): arr1.append(i)for i in range(10): print(binary_search(arr1,i))我希望得到類似的東西，'0,1,2,3,4,5,6,7,8,9'但得到'0,1,0,0,4,None ,None,2,0,0'
2 回答
波斯汪
TA貢獻1811條經驗 獲得超4個贊
你有兩個問題。第一個是錯字，你說
if (val > mid):
你應該說
if (val > arr[mid]):
由于您要比較的是值而不是索引。
第二個是更微妙的...當您檢查數組的右側時，在：
return binary_search(arr[mid+1:], val)
您傳遞給遞歸調用（arr[mid+1:]）的子數組已經在數組的中間開始，這意味著遞歸調用的結果將返回subarray中元素的索引。因此，您需要添加用于拆分數組的索引增量，以再次具有基于完整數組的索引：
return binary_search(arr[mid+1:], val) + (mid + 1)
這是完整的完整代碼：
def binary_search(arr, val):
left = 0
right = len(arr)-1
mid = (left + right)//2
#Go through the array
if (val == arr[mid]):
return mid
#Check right side of arr
if (val > arr[mid]):
return binary_search(arr[mid+1:], val) + (mid + 1)
#Check left side of arr
return binary_search(arr[:mid], val)
哆啦的時光機
TA貢獻1779條經驗 獲得超6個贊
你比較val到mid，而不是向arr[mid]。另外，如果您將ifs互斥，它會更好看。另外，按照下面的nosklo的回答，您需要為大于情況添加索引偏移量：
#Go through the array
if (val == arr[mid]):
return mid
#Check right side of arr
elif (val > mid):
return binary_search(arr[mid+1:], val) + (mid + 1)
#Check left side of arr
else:
return binary_search(arr[:mid], val)
添加回答
舉報
0/150
提交
取消