python - Python 的二分法如何工作？

Question

我读到Python 的列表是使用指针实现的。然后我看到这个模块http://docs.python.org/2/library/bisect.html它可以有效地插入到排序列表中。它是如何有效地做到这一点的？如果列表是使用指针而不是通过连续数组实现的，那么如何有效地搜索插入点呢？如果列表是通过连续数组支持的，那么在插入元素时必须进行元素移位。那么这个bisect如何有效地工作呢？

Answer 1

我相信列表的元素是指向的，但“列表”实际上是一个连续的数组(在 C 中)。它们被称为列表，但它们不是链接列表。

实际上，在排序列表中查找元素非常好 - 时间复杂度为 O(logn)。但插入并不是那么好 - 它是 O(n)。

如果你需要一个logn数据结构，最好使用treap树或红黑树。