实现二进制搜索-Java 学习之路

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

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

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

1 回答

4
两个问题：
- 当您通过调用 bisect 进行递归时，您仍需要通过执行 return bisect(list[:split],target) 来返回调用的值 .
- split 是 list 的元素，而不是索引，因此 list[:split] 将不会按您的想法执行 . 请改用 list[:len(list)//2] ，同样将 list[split:] 更改为 list[len(list)//2:] .
回复于 2024-05-20T23:16:30+08:00

实现二进制搜索

1 回答

相关问题