Python的bisect模块——数组二分查找算法

bisect 模块

bisect 模块实现了对有序数组的二分查找和插入，使用该模块插入数据时仍能保持有序。

bisect 模块源码

bisect 的源码短小精悍，也可以作为二分查找算法的示例。
整个模块去掉注释，就以下这么多代码。

"""Bisection algorithms."""

def insort_right(a, x, lo=0, hi=None):

    lo = bisect_right(a, x, lo, hi)
    a.insert(lo, x)

def bisect_right(a, x, lo=0, hi=None):

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

def insort_left(a, x, lo=0, hi=None):

    lo = bisect_left(a, x, lo, hi)
    a.insert(lo, x)

def bisect_left(a, x, lo=0, hi=None):

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

try:
    from _bisect import *
except ImportError:
    pass

bisect = bisect_right
insort = insort_right

bisect 模块的函数

注意：该模块所有函数的使用前提为列表 a 为有序数组，且是升序排序

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

在列表 a 中找到元素 x 合适的插入点以维持其有序，默认作用于整个列表，参数 lo 和 hi 可以用来更改作用的范围。
如果 x 已经在 a 里存在，那么插入点会在已存在元素的左边。返回值为插入点的索引值。（其时间复杂度是 O(log n) 的）

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

bisect.bisect(a, x, lo=0, hi=len(a))

这两个函数的作用是相同的。类似于 bisect_left() ，但是插入点是 a 中已存在元素的右边。

bisect.insort_left(a, x, lo=0, hi=len(a))

将 x 插入到列表 a ，并维持其有序。其实现是 a.insert(bisect_left(a, x, lo, hi), x) , 故其时间复杂度为 O(n) 。

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

bisect.insort(a, x, lo=0, hi=len(a))

这两个函数的作用是相同的。类似于 insort_left() ，但是是把 x 插入到 a 中已存在元素的右侧。

bisect 模块的使用

nums = [-9, -1, 0, 1, 2, 2,  4]
print(bisect.bisect_left(nums, 2))  # out: 4
print(bisect.bisect(nums, 2))  # out: 6
print(bisect.bisect_right(nums, 2))  # out: 6
# 当 lo = 5 时，要插入的 x = 2 只能从列表中索引为 5 的位置开始找合适的位置
print(bisect.bisect_left(nums, 2, 5))  # out:5
print(bisect.bisect_left(nums, -21))  # out: 0

bisect 的妙用

Python官方文档（附于参考链接）给出了一个比较巧妙的用法：

函数 bisect() 还可以用于数字表查询。这个例子是使用 bisect() 从一个给定的考试成绩集合里，通过一个有序数字表，查出其对应的字母等级：90 分及以上是 ‘A’，80 到 89 是 ‘B’，以此类推

>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
...     i = bisect(breakpoints, score)
...     return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

参考资料

• https://docs.python.org/zh-cn/3.8/library/bisect.html
• https://www.liujiangblog.com/course/python/57

ps: 欢迎浏览我的博客 www.bluewhale52.com