Python二進制搜索總是返回目標未找到的值

我已經編寫了以下代碼，對列表或元組collection中的值target執行二進制搜索。Python二進制搜索總是返回目標未找到的值

def binary(collection, target): 
    """Binary search 
    Takes a sorted list or tuple, collection, then searches for target 
    Returns -1 if item isn't found. """ 
    length = len(collection) 
    minimum = 0 
    maximum = length - 1 
    while minimum <= maximum: 
     pivot = (minimum + maximum) // 2 
     if collection[pivot] is target: 
      return pivot 
     elif collection[pivot] > target: 
      minimum = pivot + 1 
     else: 
      maximum = pivot - 1 
    return -1

正如你可以看到，當target不collection發現，函數返回-1。無論我做了什麼，函數都返回-1。

>>> test = [1, 2, 3, 4, 5, 6] 
>>> binary(test, 5) 
-1 
>>> binary(test, 1) 
-1

什麼原因導致這個問題？

來源

2010-09-11 Rafe Kettler

*雖然二進制搜索的基本思想是比較簡單，細節更是出奇地棘手* - 高德納教授。 – FMc 2010-09-11 12:21:01

Donald Knuth有沒有話題沒有引用？ – 2010-09-11 14:15:02

你有這個條件倒退：

elif collection[pivot] > target:

切換後，搜索的工作原理：

elif collection[pivot] < target:

對於它的價值，我想通了這一點通過增加打印輸出到您的搜索，看看有什麼發生。如有疑問，請添加打印輸出：

>>> binary([1, 2, 3], 1) 
(min=0, max=2, pivot=1) 
(min=2, max=2, pivot=2) 
    ^Oops 

# After fixing... 
>>> binary([1, 2, 3], 1) 
(min=0, max=2, pivot=1) 
(min=0, max=0, pivot=0)

順便說一句，內置bisect module執行二進制搜索。你不必自己寫，除非你是爲了教育價值而寫的。

來源

2010-09-11 05:22:04

純粹的教育價值。基於我記得的二進制搜索，我有點反感。 – 2010-09-11 05:28:06

我看了一下bisect模塊，看起來'bisect_left（）'可以作爲二分查找而稍作修改。謝謝你的提示。 – 2010-09-11 05:36:34

上一次我試圖編寫我自己的二進制搜索時，我花了大約10次迭代纔得到這個愚蠢的東西。逐個錯誤是我的氪石。 :-) – 2010-09-11 05:37:58

除了糾正你的條件測試elif collection[pivot] < target:，你用了「是」進行測試操作是否已經找到了你的目標項目：

if collection[pivot] is target:

你應該用「==」來代替：

if collection[pivot] == target:

使用「is」測試兩件事實際上是否是相同的對象。在Python中，經常會有小字符串和整數對象被存儲和回收，所以這可能會起作用。然而，在大多數情況下，它不會：

>>> a='abc' 
>>> id(a) 
2129839392 
>>> b='ab' 
>>> b+='c' 
>>> id(b) 
2129963136 
>>> a 
'abc' 
>>> b 
'abc' 
>>> binary([a],a) 
0 
>>> binary([a],b) 
-1

來源

2011-02-16 20:01:12 pjkundert

Python二進制搜索總是返回目標未找到的值

回答

相關問題