無限循環

Question

我試圖實現與下面的函數二進制搜索：

def buggy_binary_search(input, key): 
    low = 0 
    high = len(input)-1 
    mid = (low + high)/2 
    while low <= high: 
     if input[mid] == key: 
      return mid 
     if input[mid] > key: 
      high = mid - 1 
     else: 
      low = mid 
    return -1 

運行時，上面的功能，進入一個無限循環。我該如何糾正？

Answer 1

因爲您沒有更新mid的值，while循環會繼續檢查相同的元素並運行到無限循環，以糾正許多人已指出的更新在while循環中的mid。
此外，你應該做low = mid+1而不是low = mid。

完整的代碼下面給出： -

def binary_search(input, key): 
     low = 0 
     high = len(input)-1 
     mid = (low + high)/2 
     while low <= high: 
      mid = (low + high)/2 
      if input[mid] == key: 
      return mid 
      if input[mid] > key: 
      high = mid - 1 
      else: 
      low = mid + 1 
     return -1 

確保輸入的排序！

Answer 2

def binary_search(input, key): 
    low = 0 
    high = len(input)-1 
    mid = (low + high)/2 
    while low <= high: 
     mid = (low + high)/2 
     if input[mid] == key: 
      return mid 
     if input[mid] > key: 
      high = mid - 1 
     else: 
      low = mid + 1 
    return -1 

as Dmitry Bychenko說，你應該在循環中設置mid =（low + high）/ 2。