学习bisect模块

使用Python这么久，今天才第一次用到bisect模块，真是不应该...看来以前做的项目写的代码，都太没有技术含量了...不过说真的，bisect也只是实现了在有序序列上进行二分查找的算法而已拉，这样的算法，随时都可以手搓一个出来，不用也罢。但如何灵活应用二分查找算法，确是考验真正的算法实力。

bisect这个模块接口不多，我喜欢。首先说说下面这两个接口：

# 首先，a是有序的！

# 找出index，使得在此index上插入x，能够保持a的有序性，
# 同时，如果a中已经存在x，这个index在最左边！
# all(val<x for val in a[lo:i]) for the left side，
# all(val>=x for val in a[i:hi]) for the right side.
bisect_left(a,x,lo=0,hi=len(a),*,key=None)

# bisect_right同bisect!
# 找出index，使得在此index上插入x，能够保持a的有序性，
# 同时，如果a中已经存在x，这个index在最右边！
# all(val<=x for val in a[lo:i]) for the left side，
# all(val>x for val in a[i:hi]) for the right side.
bisect_right(a,x,lo=0,hi=len(a),*,key=None)
bisect(a,x,lo=0,hi=len(a),*,key=None)

>>> from bisect import bisect_left, bisect
>>> a = [i for i in range(10)]
>>> a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> bisect(a, 3)  # bisect_right
4
>>> bisect_left(a, 3)
3
>>> bisect(a, 30)
10
>>> bisect_left(a, 30)
10

返回的index不一定是立即合法的，只有insert之后才OK！(lo就是low，hi就是high，如果设定，就是在此区间进行操作)

二分查找的目的，最直接的就是查找和插入，bisect接口得到插入index，下面来看看如何使用此接口进行查找：

>>> a[bisect_left(a,7)] == 7  # better
True
>>> a[bisect(a,7)-1] == 7
True

我今天使用这个接口，是应用在LeetCode的第15题，三数和。用这两个接口，在一个有序序列上确定了一个遍历区间。

insort_left(a,x,lo=0,hi=len(a),*,key=None)

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

>>> from bisect import insort_left, insort
>>> a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> insort_left(a, 5)
>>> a
[0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9]
>>> insort(a, -2)
>>> a
[-2, 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9]

注意：bisect算法是\(O(\log(N))\)，但对list执行insert，是\(O(N)\)！我们一般都不会去insert一个list，只是append和pop，在list尾部操作，得到\(O(1)\)的性能。

bisect可以在排好序的顺序容器上执行，而insort只能用于mutable的顺序容器，而且还要有insert接口。下面的代码，测试接口在deque上的使用，deque容器在任意位置上的insert都是\(O(1)\)，很nice...

>>> from collections import deque
>>> d = deque()
>>> for i in range(10):
...   d.append(i)
...
>>> d
deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> bisect(d, 7)
8
>>> insort(d, 7)
>>> d
deque([0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9])

如果我们把一个list中的每个数字，当做分割区间的间隔点，另外再配合一个list，用来已同样顺序的方式表达每个区间对应的信息，用bisect接口，可轻松实现对任何输入提取其所在区间的信息。下面这段代码，来自Python官方示例：

>>> 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']