我是演算法的新手。我最近開始研究二分搜索并嘗試自己實作它。任務很簡單：我們有一個整數陣列a和一個 integer x。如果a包含x結果應該是它的索引，否則函式應該回傳-1。
這是我寫的代碼：
def binary_search(a, x):
l = 0
r = len(a)
while r - l > 0:
m = (l r) // 2
if a[m] < x:
l = m
else:
r = m
if a[l] == x:
return l
return -1
但是這段代碼在a = [1, 2]和上陷入無限回圈x = 2。我想，我有不正確的回圈條件（可能，應該是r - l >= 0），但這個解決方案沒有幫助。我哪里錯了？
uj5u.com熱心網友回復：
讓我做一些桌面檢查。我假設a = [1, 2]我們正在尋找一個 2
所以我們開始
l = 0
r = 2
由于r - l = 2 > 0，我們進入了while回圈。
m = (l r) / 2 = (0 2) / 2 = 1
a[m] = a[1] = 2 == x (hence not less than x)
r = m = 1 (and l remains the same)
現在r - l = 1 - 0 = 1 > 0，所以我們繼續
m = (l r) / 2 = (0 1) / 2 = 0
a[m] = a[0] = 1 < x
l = m = 0 (and r remains the same)
在此迭代之后，r和l都具有與之前相同的值，然后產生無限回圈。
Ashok 的回答是一個很好的解決方案。但我認為對固定代碼進行一些桌面檢查并看看有什么改進它會很有教育意義。
基本上出現問題的情況是，當l 1 = r. 然后m將始終評估為l，a[l] < x并再次l設定為m，這不會改變情況。
在較大的代碼段中，制作一個表格是有意義的，該表格包含要觀察的每個變數的列和記下已評估的代碼行的列。評論欄也無妨。
uj5u.com熱心網友回復：
正如 Mani 提到的，你沒有考慮什么時候A[m]==x。包括那個案例（那時你已經找到了a所以只需 return m），一旦你有了那個案例，l=m 1當我們仍然低于 x 時，我們可以讓。像這樣：
def binary_search(a, x):
l = 0
r = len(a)
while r - l > 0:
m = (l r) // 2
if a[m] < x:
l = m 1
elif a[m]==x:
return m
else:
r = m
if l<len(a) and a[l] == x:
return l
return -1
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/367793.html