二分算法的复杂度是什么？

Question

我编写了一些代码来测试在搜索列表中的元素时哪种方法更快。结果表明，bisect是最快的。但我不明白bisect算法的复杂度是什么，它是否使用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

Reference: http://docs.python.org/library/bisect.html

- codersofthedark

---

vEB树不仅适用于整数，而Bitsect适用于所有可比较的元素。 - user395760

Python中是否有提供vEB实现的模块？ - codersofthedark

这是一个不同的问题，最好直接问。我可以问一下你为什么需要vEB树吗？如果你不需要顺序，那么dict基本上是O(1)的。如果要求足够严格，二分查找已经不可行了（即使有数十亿个元素，O(log N)已经非常好了），难道你不想节省大量的空间和时间，而不是用Python编写它吗？ - user395760

我想在一个列表中搜索一个给定的数字，找到最接近它的数字。什么是最好的方法？ - codersofthedark

二分查找对此非常适用（你只需要考虑返回索引旁边的项），它也很容易获得。它还有一个C实现可用，因此它可能比您在Python中编写的任何内容都要好。 - user395760

对于那些需要排序值列表的算法，你的时间测试应该包括对它们进行排序（而不是预先排序）。此外，内置的 list 搜索将受到元素顺序的影响，因此为了获得统计意义的结果，你需要随机化元素的顺序。 - martineau

Answer 1

它使用二分查找算法，因此时间复杂度为O(log n)。

- Ignacio Vazquez-Abrams

Answer 2

有二分查找，对吧。答案是O(Ln(n))。

但是，你的列表不足以测试所有情况。所有算法可能需要不同的执行时间，但你必须用所有情况来测试它们。如果你用足够多的列表进行测试，你将得到正确的结果。

我希望你已经被说服了。

- totten