我已經編寫了以下代碼,對列表或元組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
什麼原因導致這個問題?
*雖然二進制搜索的基本思想是比較簡單,細節更是出奇地棘手* - 高德納教授。 – FMc 2010-09-11 12:21:01
Donald Knuth有沒有話題沒有引用? – 2010-09-11 14:15:02