此代碼僅返回目標(biāo)的位置。我還需要計(jì)算步數(shù)。我該如何修改這段代碼來實(shí)現(xiàn)我的目標(biāo)？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貢獻(xiàn)1725條經(jīng)驗(yàn) 獲得超8個(gè)贊
您可以將其添加為函數(shù)參數(shù)并遞歸更新
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貢獻(xiàn)1795條經(jīng)驗(yàn) 獲得超7個(gè)贊
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)
添加回答
舉報(bào)
0/150
提交
取消