前言

bisect模块在Python的官方库中属于小众，源码也不多，加上注释也没能超过100行。当你希望维护的列表总是有序时，bisect模块可能是不错的选择。

insort

bisect.insort()函数接受四个参数：

• a：一个有序列表
• x：需要插入的元素
• lo：默认值为0（该参数不能小于0）
• hi：默认值为列表的长（len(a)）

使用：

In [2]: lyst = [5, 1, 8, 2, 9]

In [3]: lyst.sort()  # 对列表排序

In [4]: lyst
Out[4]: [1, 2, 5, 8, 9]

In [5]: bisect.insort(lyst, 3)  # 在lyst中有序的插入3

In [6]: lyst
Out[6]: [1, 2, 3, 5, 8, 9]

bisect模块中有关插入操作的方法有两个，一个是insort_left()，一个是insort_right()。insort()方法是insort_right（）方法的缩写。

区别在于，当将要插入的元素已经存在在列表中，insort_left()方法会把元素插入到存在元素的左边，而insort_right()方法会把元素插入到存在元素的右边。

bisect

bisect.bisect()类似bisect.insort()方法，不过bisect()不做插入操作，而是返回如果插入，那么插入位置的值。

In [0]: lyst = [5, 1, 8, 2, 9]

In [1]: lyst.sort()

In [2]: bisect.bisect(lyst, 4)
Out[2]: 2

In [3]: lyst
Out[3]: [1, 2, 5, 8, 9]

bisect.bisect()是bisect.bisect_right()的缩写，另一个方法是bisect.bisect_left()。

二分查找

bisect模块中的方法基于二分查找法实现，虽然代码不多，但效率很不错。需要注意的是，如果想在自己封装的对象里使用bisect模块中的方法，需要支持insert()操作。

以下是insort的源码（bisect类似）：

def insort_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
    a.insert(lo, x)

def insort_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
    a.insert(lo, x)

感谢

• 参考慕课Bobby老师课程Python高级编程和异步IO并发编程