二進制搜索功能

晚上好。我正試圖回到編程，並決定在我自己的時間做一些練習編碼。我目前正在嘗試實現二進制搜索，但似乎在我的代碼中有一個連續的循環。有人能給我一個關於發生了什麼的暗示嗎？二進制搜索功能

def binChop(key, ordered_set): 

    found = False 
    newSet = ordered_set 

    while found != True or newSet > 0: 
     midpoint = int(len(newSet)/2) 
     if key < newSet[midpoint]: 
      found = False 
      newSet = newSet[:midpoint] 
     elif key > newSet[midpoint]: 
      found = False 
      newSet = newSet[midpoint:] 
     elif key==newSet[midpoint]: 
      found = True 
    return found

來源

2012-10-31 Cipher

還有，如果集被減少爲單個元件（或零種元素）沒有有效的退出條件和檢索關鍵字是未找到。（*編輯*：除非'newSet> 0'確實檢查'len（newSet）> 0';'ordered_set'的類型是什麼？） – mgibsonbr

這是我完成的不同編輯的錯誤。感謝您的追捕，但它仍然在一個無休止的循環處：（ – Cipher

我認爲你的問題是在while循環的條件。你有'或'而不是'和' - 這意味着即使你找到你的結果，newSet> 0條件也會得到滿足。

來源

2012-10-31 22:11:17 Matt

這似乎工作。不幸的是我不能讓它返回False，如果一個數字不在集合中，只是循環，這應該縮小爲我感謝你的幫助。 – Cipher

我懷疑「newSet> 0」總是如此。如果這是一個標準的Python集，你會得到一個錯誤：

>>> b=set() 
>>> b 
set([]) 
>>> b > 0 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
TypeError: can only compare to a set

但既然你不這樣做，我想這是一個列表或元組：

>>> a=[] 
>>> a > 0 
True 
>>> b=() 
>>> b > 0 
True

哪個都沒有做什麼你期望（檢查長度）。

一般來說，將import pdb; pdb.set_trace()添加到代碼中並逐步找出錯誤。

來源

2012-10-31 22:12:57 lynxlynxlynx

太棒了。感謝你的領導。這會派上用場 – Cipher

您有可以改進的幾個問題和一些：

您需要的左右邊界指標正確執行二進制搜索時，該元素是不是在有序列表。請參閱正確的算法here。當您找到您的鑰匙或左側邊界位於右側邊界右側時，您可以離開while循環（max_point < min_point）。
您不需要newSet。您始終可以在排序列表中使用索引。所以mid_point只是一個索引，min_point（左邊界）和max_point（右邊界）也是如此。
二分搜索通常返回鍵的索引作爲返回。如果沒有找到，請返回-1。

我的Python代碼如下所示：

def binChop(key, ordered_list): 

    min_point, max_point = 0, len(ordered_list)-1 

    while min_point <= max_point: 
     mid_point = (min_point+max_point)/2 

     if ordered_list[mid_point] < key: 
      min_point += 1 
     elif ordered_list[mid_point] > key: 
      max_point -= 1 
     else: 
      return mid_point 
    return -1 

test_cases = [[], [5], [4,5], [5,6], [1,5,6], [1], [1,4], [1,6,15]] 
for ordered_list in test_cases: 
    print "%-10s %5s" % (ordered_list, binChop(5, ordered_list))

Outputs: 
list  index of 5 
[]   -1 
[5]   0 
[4, 5]   1 
[5, 6]   0 
[1, 5, 6]  1 
[1]   -1 
[1, 4]  -1 
[1, 6, 15] -1

來源

2012-11-01 05:47:24 greeness

二進制搜索功能

回答

相關問題