此代碼僅返回目標的位置。我還需要計算步數。我該如何修改這段代碼來實現我的目標？def binary_search(arr, low, high, x): if high >= low: mid = (high + low) // 2 if arr[mid] == x: return mid elif arr[mid] > x: return binary_search(arr, low, mid - 1, x) else: return binary_search(arr, mid + 1, high, x) else: return -1 LT = [1,2,3,4,5,6,7,8,9,10]pos = binary_search(LT,0,9,5)print(str(pos))
2 回答
qq_遁去的一_1
TA貢獻1725條經驗 獲得超8個贊
您可以將其添加為函數參數并遞歸更新
def binary_search(arr, low, high, x, steps = 0):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
print(f"found at {steps} steps")
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x, steps + 1)
else:
return binary_search(arr, mid + 1, high, x, steps + 1)
else:
return -1
一只萌萌小番薯
TA貢獻1795條經驗 獲得超7個贊
Python 中的二分搜索代碼，無需遞歸：
def binary_search_itr(arr, size, val,step=0):
ln=0
r = size-1
mid = (ln + r) // 2
while (arr[mid] != val and ln <= r):
if val < arr[mid]:
step = step + 1
r = mid - 1
else:
step = step + 1
ln = mid + 1
mid = (ln + r) // 2
if arr[mid] == val:
step = step + 1
return mid,step
return -1
LT = [1,2,3,4,5,6,7,8,9,10]
pos = binary_search_itr(LT,9,9)
print(pos)
添加回答
舉報
0/150
提交
取消