Python 二分查找库 bisect

为为为什么

发布于 2023-10-18 16:01:23

2210

发布于 2023-10-18 16:01:23

文章被收录于专栏：又见苍岚

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

bisect

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

查找方法

bisect_left

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

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)

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

bisect / bisect_right

bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)

类似用法，在右侧。

插入方法

insort_left

bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)

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

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

insort /insort_right

bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)

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

性能

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

示例

查找

import bisect
a = [[1, 'asdf'], [2, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]

bisect.bisect_right(a, 7, key=lambda x:x[0])

-->
4

插入

import bisect

a = [[1, 'asdf'], [2, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]
bisect.insort_left(a, [6, '###'], key=lambda x:x[0])

-->
[[1, 'asdf'], [2, 'asdf'], [4, 'asdf'], [6, '###'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]