bisect算法的复杂度是多少?

本文介绍了bisect算法的复杂度是多少?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我编写了代码，以了解在搜索列表中的元素时哪个更快.事实证明是二等分的.我不明白什么是bisect算法的复杂性，它使用Van Emde Boas树吗?

I wrote code to understand which of them is faster when it comes to search an element in a list. It turns out to be bisect. What I do not understand is what is complexity of bisect algorithm and does it use Van Emde Boas tree?

#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

参考: docs.python/library/bisect.html

推荐答案

它使用二进制搜索，从而使其变为O(log n).

It uses binary search, which makes it O(log n).