本文记录 python 二分查找库 bisect 用法。

bisect {#bisect}

• 此模块支持按排序顺序维护列表，而不必在每次插入后对列表进行排序。对于具有昂贵比较操作的长列表项，这可能是对更常用方法的一种改进。

查找方法 {#查找方法}

bisect_left {#bisect-left}

在 a 中找到 x 的插入点以维持排序顺序。

参数 lo 和 hi 可用于指定应该考虑的列表的子集; 默认情况下使用整个列表。如果 x 已经存在于 a 中，则插入点将位于任何现有条目之前(左侧)。假设 a 已经排序，返回值适合作为 list.insert() 的第一个参数使用。

**bisect **/ bisect_right {#bisect-bisect-right}

类似用法，在右侧。

插入方法 {#插入方法}

insort_left {#insort-left}

按排序顺序将 x 插入 a 中。

该函数首先运行 bisect_left() 来定位插入点。接下来，它在 a 上运行 insert ()方法，在适当的位置插入 x 以维护排序顺序。

insort /insort_right {#insort-insort-right}

该函数首先运行 bisect_right() 来定位插入点。接下来，它在 a 上运行 insert() 方法，在适当的位置插入 x 以维护排序顺序。

性能 {#性能}

搜索性能为 O(log(n))， 插入为 O(n)，这是由于插入操作本身的操作复杂度决定的。

示例 {#示例}

查找 {#查找}

插入 {#插入}

参考资料 {#参考资料}

• https://docs.python.org/3/library/bisect.html

文章链接：
https://www.zywvvd.com/notes/coding/python/python-bisect/python-bisect/