Python 的 bisect 模块

bisect 模块用于维护有序列表。其实现了一个算法用于插入元素到有序列表。较为准确来说，它采用二分法来排序插入。
先来看一看有哪些方法：

>>> import bisect
>>> dir(bisect)
['bisect', 'bisect_left', 'bisect_right', 
'insort', 'insort_left', 'insort_right']
# 注，一些双下划线开头的方法没列出来

bisect 返回要插入元素在列表中的下标。假定列表是有序的。
bisect_left 与 bisect 类似，只不过其默认将元素插到左边，所以返回的是插入到左边的下标
bisect_right与 bisect_left 相反。
以上方法若列表无序，那么会返回插入到列表最后一个合适的位置。
insort 会在列表中插入元素到正确位置，假定列表有序。如果列表无序，那么会返回空。默认插入到右边。
insort_left 和insort_right 类似。

测试
接下来我们来看一看源码：

# 省略注释
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

bisect = bisect_right 
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)

注意到 bisect 就是 bisect_right。而 insort 就是 insort_right
这里是一个标准的二分查找。而 insort 采用的就是先利用二分查找找出其下标，然后调用 insert 插入。
Python 还有一个 C 版本的 bisect，它更快。在 _bisect.py 里。别问我怎么知道的，看源码就了解了。
那我们来看一看这道 Lettcode 题：
Search Insert Position
就是找到一个数在数组中的下标，如果没有那么找出其插入下标。

import bisect
a = bisect.bisect(nums, target)
if nums[a-1] == target:
    return a-1
else:
    return a

或者一行代码
len([x for x in nums if x<target])