Python中的二進制搜索實現

Question

我正在嘗試使用二分查找來實現解決方案。我有

list = [1, 2, 3, 4, 6] 
value to be searched = 2 

我寫了這樣的事情

def searchBinary(list, sval): 
    low = 0 
    high = len(list) 

    while low < high: 
     mid = low + math.floor((high - low)/2) 

     if list[mid] == sval: 
      print("found : ", sval) 
     elif l2s[mid] > sval: 
      high = mid - 1 
     else: 
      low = mid + 1 

，但是當我試圖實現這一點，我得到這樣的錯誤號的列表：索引超出範圍。請幫助確定問題。

Answer 1

有幾件事。

1. 您的命名不一致。此外，不要使用list作爲變量名稱，而是隱藏全局內置。

2. 停止條件是while low <= high。這個很重要。

3. 當您找到一個值時，您不會中斷。這將導致無限遞歸。

---

def searchBinary(l2s, sval): # do not use 'list' as a variable 
    low = 0 
    high = len(l2s) 

    while low <= high: # this is the main issue. As long as low is not greater than high, the while loop must run 
     mid = (high + low) // 2 

     if l2s[mid] == sval: 
      print("found : ", sval) 
      return 
     elif l2s[mid] > sval: 
      high = mid - 1 
     else: 
      low = mid + 1 

而現在，

list_ = [1, 2, 3, 4, 6] 
searchBinary(list_, 2) 

輸出：

found : 2 

Answer 2

UPDATEhigh = len(lst) - 1每下面的評論。

---

三個問題：

1. 您使用l2s代替list（參數的實際名稱）。
2. 您的while條件應該是low <= high而不是low < high。
3. 您應該在找到該值時返回索引，如果找不到則返回None（或者可能是-1？）。

一對夫婦的其他小的變化我做：

• 這是一個壞主意，隱藏內置list。我將參數重命名爲lst，在這種情況下，這在Python中通常使用。
• mid = (low + high) // 2是找到中點的更簡單形式。
• Python約定是使用snake_case，而不是camelCase，所以我重命名了這個函數。

固定碼：

def binary_search(lst, sval): 
    low = 0 
    high = len(lst) - 1 

    while low <= high: 
     mid = (low + high) // 2 

     if lst[mid] == sval: 
      return mid 
     elif lst[mid] > sval: 
      high = mid - 1 
     else: 
      low = mid + 1 

    return None 

print(binary_search([1, 2, 3, 4, 6], 2)) # 1