本文记录 python 二分查找库 bisect 用法。
在 a 中找到 x 的插入点以维持排序顺序。
bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)
参数 lo 和 hi 可用于指定应该考虑的列表的子集; 默认情况下使用整个列表。如果 x 已经存在于 a 中,则插入点将位于任何现有条目之前(左侧)。假设 a 已经排序,返回值适合作为 list.insert()
的第一个参数使用。
bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)
类似用法,在右侧。
bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)
按排序顺序将 x 插入 a 中。
该函数首先运行 bisect_left()
来定位插入点。接下来,它在 a 上运行 insert ()方法,在适当的位置插入 x 以维护排序顺序。
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']]