bisect数组的二分算法
bisect.bisect_left(a, x, lo=0, hi=len(a))
对有序列表a里插入元素x，保持有序不变，返回插入的位置。参数lo和hi是表示判断列表的范围，默认是整个范围。如果插入的元素x已经在列表a存在，那就插入在存在元素的左边。
例子：
#Python 3.4
import bisect
l = [8, 5, 6, 6, 3]
l.sort()
print(l)
print(bisect.bisect_left(l, 0))
print(l)
print(bisect.bisect_left(l, 5))
print(bisect.bisect_left(l, 7))
结果输出如下：
[3, 5, 6, 6, 8]
0
[3, 5, 6, 6, 8]
1
4
bisect.bisect_right(a, x, lo=0, hi=len(a))
bisect.bisect(a, x, lo=0, hi=len(a))
在有序队列a里查找x可以插入的位置，并保持队列有序。如果插入的值与队列里的值相同，则插入在相同元素的右边，把这个位置的索引值返回。
例子：
#python 3.4
import bisect
l = [8, 5, 6, 6, 3]
l.sort()
print(l)
print(bisect.bisect_right(l, 0))
print(l)
print(bisect.bisect(l, 5))
print(bisect.bisect(l, 7))
结果输出如下：
[3, 5, 6, 6, 8]
0
[3, 5, 6, 6, 8]
2
4
bisect.insort_left(a, x, lo=0, hi=len(a))
插入一个元素x到队列a，并把把队列排序。要当于：a.insert(bisect.bisect_left(a, x, lo, hi), x)。
例子：
#python 3.4
import bisect
l = [8, 5, 6, 6, 3]
l.sort()
print(l)
bisect.insort_left(l, 0)
print(l)
bisect.insort_left(l, 5)
print(l)
bisect.insort_left(l, 7)
print(l)
结果输出如下：
[3, 5, 6, 6, 8]
[0, 3, 5, 6, 6, 8]
[0, 3, 5, 5, 6, 6, 8]
[0, 3, 5, 5, 6, 6, 7, 8]
bisect.insort_right(a, x, lo=0, hi=len(a))
bisect.insort(a, x, lo=0, hi=len(a))
插入元素x到a队列里，如果发现有相同元素，就插入到相同元素的右边。
例子：
#python 3.4
import bisect
l = [8, 5, 6, 6, 3]
l.sort()
print(l)
bisect.insort_right(l, 0)
print(l)
bisect.insort(l, 5)
print(l)
bisect.insort(l, 7)
print(l)
结果输出如下：
[3, 5, 6, 6, 8]
[0, 3, 5, 6, 6, 8]
[0, 3, 5, 5, 6, 6, 8]
[0, 3, 5, 5, 6, 6, 7, 8]
使用上面的函数进行一些简单的封装：
def index(a, x):
'Locate the leftmost value exactly equal to x'
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
raise ValueError
def find_lt(a, x):
'Find rightmost value less than x'
i = bisect_left(a, x)
if i:
return a[i-1]
raise ValueError
def find_le(a, x):
'Find rightmost value less than or equal to x'
i = bisect_right(a, x)
if i:
return a[i-1]
raise ValueError
def find_gt(a, x):
'Find leftmost value greater than x'
i = bisect_right(a, x)
if i != len(a):
return a[i]
raise ValueError
def find_ge(a, x):
'Find leftmost item greater than or equal to x'
i = bisect_left(a, x)
if i != len(a):
return a[i]
raise ValueError
使用来对学生成绩转换为ABCDF等级：
#python 3.4
import bisect
def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
i = bisect.bisect(breakpoints, score)
return grades[i]
print([33, 99, 77, 70, 89, 90, 100])
print([grade(score) for score in [33, 99, 77, 70, 89, 90, 100]])
结果输出如下：
[33, 99, 77, 70, 89, 90, 100]
['F', 'A', 'C', 'C', 'B', 'A', 'A']