11

我编写了代码来了解在搜索列表中的元素时哪个更快。原来是平分的。我不明白二分算法的复杂性是什么，它是否使用 Van Emde Boas 树？

#python inbuilt list search using 'in' took 0.0702499200317 secs

def mul3():
    a = [1, 2, 4, 5, 6, 7, 8, 10, 12, 42, 55, 65, 69, 95, 96, 101, 156, 199]
    for x in a:
        if x in a:
            print x, "True"
        else:
            print x, "False"

#using bisect took 0.0649611193601

def mul4():
    a = [1, 2, 4, 5, 6, 7, 8, 10, 12, 42, 55, 65, 69, 95, 96, 101, 156, 199]
    import bisect
    for x in a:
        locate = bisect.bisect_left(a, x)
        if locate == len(a) or a[locate] != x:
            print False
        print True

 #using binary search took 0.0651483638284


a = [1, 2, 4, 5, 6, 7, 8, 10, 12, 42, 55, 65, 69, 95, 96, 101, 156, 199]


for x in a:
    lo = 0
    hi = 18
    while lo < hi:
        mid = (lo+hi)//2
        midval = a[mid]
        if midval < x:
            lo = mid+1
        elif midval > x:
            hi = mid
        else:
            print True
            lo = hi

参考： http ://docs.python.org/library/bisect.html

4

2 回答 2

23

它使用二进制搜索，这使得它 O(log n)。

于 2012-08-18T21:08:44.390 回答
1

有二分搜索，对。O(Ln(n))就是答案。

但是，您的列表不足以测试所有案例。所有算法可能需要不同的执行时间，但你必须在所有情况下测试这些。如果您使用足够多的列表进行测试，您将获得正确的结果。

我希望你被说服。

于 2012-08-18T22:09:58.240 回答