執行二進制搜索

我試圖執行二進制搜索;它需要一個有序列表，取中間值，將其與目標值進行比較，然後在中間值以上或以下列出子列表，直到找到目標或從列表中找不到目標。然而，出於某種原因，除非中點是目標，否則我總是會得到'無'。我不確定發生了什麼問題。執行二進制搜索

def bisect(list,target): 


    print list 
    split= list[len(list)//2] 
    print "Split value : " + str(split) 

    if target==split: 
     return "target" 

    elif target<split: 
     bisect(list[:split],target) 

    elif target>split: 
     bisect(list[(split):],target) 

a= [1,2,3,4,5,6,7,8,9,10]  
print bisect(a,2) 

Output: 

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 
Split value : 6 
[1, 2, 3, 4, 5, 6] 
Split value : 4 
[1, 2, 3, 4] 
Split value : 3 
[1, 2, 3] 
Split value : 2 
None

它看起來像分裂和目標值之間的最後一次比較沒有發生？

來源

2013-05-10 user856358

爲什麼不使用[bisect]（http://docs.python.org/2/library/bisect.html）模塊？ – 2013-05-10 19:14:55

@FredrikPihl或至少 - 看看「bisect」模塊如何實現它的功能進行比較 – 2013-05-10 19:15:28

作爲一個方面說明：調用你的列表'list'令人困惑，並且意味着你不能使用同名的類型/構造函數在你的功能。 – abarnert 2013-05-10 19:24:25

兩個問題：通過調用bisect

當你遞歸，你仍然需要回做return bisect(list[:split],target)的呼叫的價值。
split是list的元素，而不是索引，所以list[:split]不會做你的想法。改爲使用list[:len(list)//2]，並同樣將list[split:]更改爲list[len(list)//2:]。

來源

2013-05-10 19:17:42 jwodder

執行splitpoint = len（list）// 2，然後執行split = list [splitpoint]並使用list [：splitpoint]和list [splitpoint：]，會更好，而不是重複相同的表達3次。但是，否則，很好的答案。 – abarnert 2013-05-10 19:25:49

@abarnert'list [：splitpoint]'和'list [splitpoint + 1：]'。省略+1會導致無限遞歸。 – 2013-05-10 19:29:52

執行二進制搜索

回答

相關問題