bisect

Python自带的一个二分库，列表有序时使用

import bisect

>>> a = [1, 2, 2, 2, 3]
>>> pos = bisect.bisect_left(a, 2)
>>> pos
1
>>> a[pos]
2

>>> a = [1, 2, 2, 2, 3]
>>> pos = bisect.bisect_right(a, 2)
>>> pos
4
>>> a[pos]
3

>>> a = [1, 2, 2, 2, 3]
>>> bisect.bisect_right(a, 2) - bisect.bisect_left(a, 2)
3

# 查找插入位置时间复杂度O(logn), 插入元素时间复杂度O(n)
>>> a = [1, 2, 2, 2, 4]
>>> bisect.insort(a, 3)
>>> a
[1, 2, 2, 2, 3, 4]