python - bisect算法的复杂度是多少？

Question

我编写代码是为了了解在搜索列表中的元素时哪一个更快。结果是平分的。我不明白的是什么是二分法算法的复杂度，它是否使用 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

Answer 1

它使用二进制搜索，使其成为 O(log n)。