bisect 模块包含两个主要函数（ bisect 和 insort），它们内部利用二分查找算法，分别用于在有序序列中查找元素与插入元素。
bisect /baɪˈsekt/
to divide sth into two equal parts 对半分；二等分
1 bisect 函数
Luciano Ramalho 举了这样一个在干草垛中找针的示例来说明如何使用 bisect.bisect 与 bisect.bisect_left。
HAYSTACK = [1, 4, 5, 6, 8, 12, 15, 20, 21, 23, 23, 26, 29, 30]
NEEDLES = [0, 1, 2, 5, 8, 10, 22, 23, 29, 30, 31]
ROW_FMT = '{0:2d} @ {1:2d} {2}{0:<2d}'
def demo(bisect_fn):
for needle in reversed(NEEDLES):
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)
运行结果：
DEMO: bisect_right
haystack -> 1 4 5 6 8 12 15 20 21 23 23 26 29 30
31 @ 14 | | | | | | | | | | | | | |31
30 @ 14 | | | | | | | | | | | | | |30
29 @ 13 | | | | | | | | | | | | |29
23 @ 11 | | | | | | | | | | |23
22 @ 9 | | | | | | | | |22
10 @ 5 | | | | |10
8 @ 5 | | | | |8
5 @ 3 | | |5
2 @ 1 |2
1 @ 1 |1
0 @ 0 0
Python 函数的一个特点是可以把函数名作为入参，比如示例中的 bisect_fn。这样做让函数变得更加灵活，我们可以把函数名作为程序运行参数，动态加载。
HAYSTACK 是干草垛堆，NEEDLES 是针堆。在干草垛中找针，本质上是在已排好序的数列中，找某个数。
自定义的 demo(bisect_fn) 函数，首先算出 position，然后利用位置计算出需要几个分隔符号作为打印偏移量，最后按照定义好的格式打印出来。
str.format() 用于格式化字符串，它可以指定实参位置。类似 {0:2d} 的语法中的 0 表示第一个入参，:2d 表示总长度，如果不足，以空格作为占位符；d 表示十进制有符号整数。
str.format() 格式中还可以设定对齐方式。^、<、>分别表示居中、左对齐、右对齐。所以 {0:<2d} 表示第 1 个入参左对齐且占两位的十进制有符号整数。
__name__ 是 python 的内置类属性，存在于一个 python 程序中，代表对应程序名称。如果是主线程，那么它的内置名称就是 __main__。
如果在运行程序时加上 left 参数，那么在程序自定义的函数内部就会调用 bisect_left 函数。bisect 函数其实是 bisect_right 函数的别名。
bisect_left 函数与bisect 函数之间的区别是：
- bisect_left 函数会返回原序列中跟被插入元素相等的元素位置，如果插入新元素，那么这个新元素会被放置在与它相等的元素前面。
2.bisect 函数会返回原序列中跟被插入元素相等的元素之后的位置，如果插入新元素，那么这个新元素会被放置在与它相等的元素后面。
bisect_left 函数运行结果：
DEMO: bisect_left
haystack -> 1 4 5 6 8 12 15 20 21 23 23 26 29 30
31 @ 14 | | | | | | | | | | | | | |31
30 @ 13 | | | | | | | | | | | | |30
29 @ 12 | | | | | | | | | | | |29
23 @ 9 | | | | | | | | |23
22 @ 9 | | | | | | | | |22
10 @ 5 | | | | |10
8 @ 4 | | | |8
5 @ 2 | |5
2 @ 1 |2
1 @ 0 1
0 @ 0 0
python 官方文档还举了一个利用 bisect 函数，来输出考试成绩的示例程序：
def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
i = bisect.bisect(breakpoints, score)
return grades[i]
if __name__ == '__main__':
results = [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
logging.info('results -> %s', results)
运行结果：
INFO - results -> ['F', 'A', 'C', 'C', 'B', 'A', 'A']
自定义的 grade() 定义了三个参数：
| 参数名 | 说明 |
|---|---|
| score | 考试分数 |
| breakpoints | 分数等级边界值；这里分为 5 档；90 及以上、80 ~ 89、70 ~ 79、60 ~ 69 以及 60 以下。 |
| grades | 评测分范围。 |
grade() 函数首先根据传入的分数，通过 bisect() 函数找出其所在位置，然后把这一位置传入 grades 序列得到评测分。
在主线程中，通过 for in 语法迭代表示学生成绩的序列，把成绩传入 grade() 函数计算出评测分，最后通过序列一次性输出。
2 insort 函数
因为排序是一项很耗时的工作，所以对于一个有序的序列来说，新增一个元素时，最好是仍然保持有序。 insort 函数在插入时，会确保这个序列始终有序。
SIZE=10
my_list=[]
for i in range(SIZE):
new_item=random.randrange(SIZE*3)
bisect.insort(my_list,new_item)
print('%2d -> '% new_item,my_list)
运行结果：
18 -> [18]
8 -> [8, 18]
21 -> [8, 18, 21]
5 -> [5, 8, 18, 21]
19 -> [5, 8, 18, 19, 21]
13 -> [5, 8, 13, 18, 19, 21]
20 -> [5, 8, 13, 18, 19, 20, 21]
4 -> [4, 5, 8, 13, 18, 19, 20, 21]
15 -> [4, 5, 8, 13, 15, 18, 19, 20, 21]
2 -> [2, 4, 5, 8, 13, 15, 18, 19, 20, 21]
randrange() 会返回给定入参范围内的随机数，但不包括边界值。
可以看到，每次插入时，序列始终保持有序。
print('%2d -> '% new_item,my_list) 采用了 %s 格式化语法，%2d 定义了 new_item 值的格式，而 my_list 会自动挂在格式之后。所以这里在第二个百分号之后没有加上括号，圈出需要格式化的参数。
insort 也有个兄弟叫 insort_left，底层使用的是 bisect_left。insort_left 函数会把新元素放置在与它相等的元素前面。
另外 bisect 函数与insort 函数，都有两个可选参数（lo 与 hi），利用它们可以缩小需要查找的序列范围。lo 的默认值是 0，hi 的默认值是序列的长度。
