python - 实现二分查找

Question

我正在尝试实现二进制搜索；它需要一个有序列表，获取中间值，将其与目标值进行比较，然后在中间值之上或之下列出子列表，直到找到目标或从列表中丢失。但是，出于某种原因，除非中点是目标，否则我总是返回“无”。我不确定出了什么问题。

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

看起来拆分和目标值之间的最后一次比较没有发生？

Answer 1

两个问题：

1. 当你通过调用进行递归时bisect，你仍然需要通过doing返回return bisect(list[:split],target)调用的值。

2. split是 的一个元素list，而不是一个索引，所以list[:split]不会按照你的想法去做。改为使用list[:len(list)//2]，同样更改list[split:]为list[len(list)//2:].