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 进行递归时，您仍然需要返回调用的值，方法是执行 return bisect(list[:split] ,目标)。

2. split 是 list 的一个元素，而不是索引，所以 list[:split] 不会做你想做的事思考。请改用 list[:len(list)//2]，同样将 list[split:] 更改为 list[len(list)//2: ].