錯誤在Python二進制搜索算法使用僞

-1

所以我想做一個遞歸二進制搜索算法和這裏的時候是我使用的僞代碼：錯誤在Python二進制搜索算法使用僞

BINARY-SEARCH(X, A, start, end) 
1 if start > end then 
2  return False 
3 middle = ((end - start)/2) + start 
4 if X = A[middle] then 
5  return True 
6 else if X < A[middle] then 
7  return BINARY-SEARCH(X, A, start, middle - 1) 
8 else 
9  return BINARY-SEARCH(X, A, middle + 1, end)

，這裏是我的程序：

def binarySearchRec(value, list, start, end): 
    if start > end: 
     return False 
    middle = ((end - start)/2) + start 
    if value == list[middle]: 
     return True 
    elif value < list[middle]: 
     return binarySearchRec(value, list, start, middle - 1) 
    else: 
     return binarySearchRec(value, list, middle + 1, end)

，所以我不斷收到的索引錯誤，每當我使用的值是不在列表中，但它工作正常，發現是在列表中的值，任何幫助將不勝感激

來源

2015-11-13 student

提示：Python的列表是零索引 – miraculixx

您能舉例說明價值，列表，開始和結束該產品的例外情況嗎？此外，您可能希望使用列表以外的變量名稱，因爲您正在跺跺內置類型。當我使用列表類型時，通常使用數據作爲名稱。 –

僞代碼使用包含上限，這意味着「結束」是一個有效的索引。您必須將'len（a） - 1'作爲'end'參數傳遞。 –

你使用' STA rt'和'結束'？我剛剛運行了你的函數，它對列表中不存在的值運行良好（返回False）。

來源

2015-11-13 21:50:39 Darya

因爲答案已經送人了已經，我建議你嘗試從另一個角度解決這個問題 - 通過測試它：

每當我使用的值不在列表中，但它工作正常查找用於在列表中

值有趣的代碼不上陣列中的每一個失敗數不。試用array = range(1,10,2)並搜索例如2，4，6，8 - 全部不在陣列中。它會工作。搜索10，它會失敗。這暗示着極限檢查可能是錯誤的，而不是像這樣的實現。

任何幫助，將不勝感激

這裏是一個測試你的功能，並很快看到什麼號碼是失敗的方式：

from itertools import izip_longest as izipl 
def complement(a): 
    return list(set(range(min(a), max(a) + 10)) - set(a)) 
array = range(1,10,2) 
c_array = complement(array) 
start = 0 
end = len(array) # that's the culprit 
try: 
    for a,b in izipl(array, c_array): 
     if a: 
      assert binarySearchRec(a, array, start, end), "expected to find %s" % a 
     if b: 
      assert not binarySearchRec(b, array, start, end), "did not expect to find %s" % b 
     print "worked on", a, b 
except: 
    print "failed on", a, b 
else: 
    print "all is well" 
=> 
worked on 1 2 
worked on 3 4 
worked on 5 6 
worked on 7 8 
failed on 9 10

來源

2015-11-13 22:07:12 miraculixx

錯誤在Python二進制搜索算法使用僞

回答

相關問題