执行二进制搜索

我试图执行二进制搜索;它需要一个有序列表，取中间值，将其与目标值进行比较，然后在中间值以上或以下列出子列表，直到找到目标或从列表中找不到目标。然而，出于某种原因，除非中点是目标，否则我总是会得到'无'。我不确定发生了什么问题。执行二进制搜索

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

执行二进制搜索

回答

相关问题