執行二進制搜索算法

Question

對於使用此二進制搜索功能的較大數據集，我得到一個索引錯誤。當我輸入一個較小的數據集，即[1,2,3,4,5]搜索5時，算法按預期運行。然而，當我拿到下面的文本時，用空參數列表（delimeter char是''）調用字符串對象的split方法，並將字符串分解爲一個列表值，其中每個元素都是一個字符串，然後搜索單詞'過失」我結束了以下錯誤：

IndexError：列表索引超出範圍

幫助深表感謝。謝謝。

string： 1. Lorem ipsum dolor sit amet，consectetur adipisicing elit，sed do eiusmod tempor incididunt ut labore et dolore magna aliqua。請將您的評論發送給我們，我們會盡快爲您解答。 Duis aute irure dolor in renhenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur。 Excepteur sint occaecat cupidatat non proident，sunt in culpa qui officia deserunt mollit anim id est laborum。

代碼： http://ideone.com/TXVfQA

def binary_search(l,skey,start,stop): 
    length = (stop - start) + 1 # length of search space 
    middle = start + (length/2) 
    mid_val = l[middle] 
    if skey == mid_val: 
     return middle 
    elif skey > middle: 
     return binary_search(l,skey,(middle + 1),stop) 
    else: 
     return binary_search(l,skey,start,(middle - 1)) 

Answer 1

這個算法有幾個問題。

首先，如果您要求列表中小於最小的項目（skey < l[start]），則它會循環。 二，當skey not in l[start:stop]時，則搜索與索引超出界限。

對於列表中未顯示元素的情況，您沒有適當的行爲。例如，如果找不到元素，則可以返回None。你的代碼可以固定的方式：

def binary_search(l, skey, start, stop): 
    # possible answer is always in interval [start, stop) 
    while start + 1 != stop: 
     middle = (start + stop) // 2 
     mid_val = l[middle] 
     if skey < mid_val: 
      stop = middle 
     else: 
      start = middle 
    return start if l[start] == skey else None 

它會找到元素等於skey的最後一次出現。它也使用循環代替遞歸，節省執行函數所需的時間。

Answer 2

你永遠檢查，看看是否stop小於start。您的遞歸調用將輕鬆創建該條件。