bisect模块

bisect模块包含两个主要函数，bisect和insort，两个函数都利用二分查找算法来在有序的序列中查找或插入元素。

用bisect搜索

在有序序列中用bisect 查找某个元素的插入位置：

import bisect
import sys

HAYSTACK = [1,4,5,6,8,12,15,20,21,23,26,29,30]
NEEDLES = [0,1,2,10,22,30,31]
ROW_FMT = '{0:2d} @ {1:2d} {2}{0:<2d}'
def demo(bisect_fn):
    for needle in reversed(NEEDLES):
        #用特定的bisect函数来计算元素应该出现的位置
        position = bisect_fn(HAYSTACK,needle)
        offset = position * '  |'
        # 把元素和其应该出现的位置打印出来
        print(ROW_FMT.format(needle,position,offset))
        


if __name__ == '__main__':
    if sys.argv[-1] == 'left':
        bisect_fn = bisect.bisect_left
    else:
        bisect_fn = bisect.bisect
        
    print('DEMO:',bisect_fn.__name__)  #把选定的函数打印出来
    print('haystack ->',' '.join('%2d' % n for n in HAYSTACK))
    demo(bisect_fn)

?

实际应用

import bisect

#根据一个分数，找到对应的成绩
def grade(score,breakpoints = [60,70,80,90],grades="FDCBA"):
    #找到分数在breakpoints中的位置
    i = bisect.bisect(breakpoints,score)
    #用该位置找到grade中对应的成绩，并返回
    return grades[i]


print([grade(score) for score in [22,63,75,98]])

# ['F','D','C','F','A']

?

?

用bisect.insort插入新元素

排序很耗时，因此在得到一个有序序列之后，我们最好能够保持它的有序。bisect.insort 就是为了这个而存在的。

insort(seq,item)

把变量item 插入到序列seq 中，并能保持seq 的升序顺序。

# insort 可以保持有序序列的顺序
import bisect
import random

SIZE = 8
#seed() 方法改变随机数生成器的种子,使random() 生成的随机数相同
random.seed(7)
#原有列表（有序）
my_list = []
for i in range(SIZE):
    #randrange()函数在一定的范围内产生随机数
    new_item = random.randrange(SIZE*2) 
    # 在列表中插入元素，并保持列表有序
    bisect.insort(my_list,new_item)
    print('%2d -> '% new_item,my_list)