【Python】bisect二分查找
程序员文章站
2024-03-19 21:40:28
...
流畅的python 2.8
bisect搜索
bisect可以在一个列表中查找一个可以插入某元素的位置,并且该位置可以保持插入元素之后,列表依旧保持升序。
可以使用bisect查找位置index,然后使用list.insert(index, value)。也可以直接使用insort完成。
lists1 = [1,3,5,7,9]
lists2 = [2,4,6,7,8]
PRINT_FMT = '{0:2d} @ {1:2d} {2}{0:2d}'
def demo(bis_fn):
for index,value in enumerate(lists2):
pos = bis_fn(lists2, value) #lists1中查找value的pos
offset = pos * ' |' #打印分隔符
print(PRINT_FMT.format(value, pos, offset))
if __name__ == '__main__':
print('lists1 -> ', ' '.join('%2d' % n for n in lists1))
demo(bisect.bisect)
打印如下:
lists1 -> 1 3 5 7 9
2 @ 1 | 2
4 @ 2 | | 4
6 @ 3 | | | 6
7 @ 4 | | | | 7
8 @ 5 | | | | | 8
使用insort
排序很耗时,因此在得到一个有序序列之后,我们最好能够保持它的有序。bisect.insort 就是为了这个而存在的。
lists3 = []
def insert():
for i in range(7):
item = random.randrange(20)
bisect.insort(lists3, item)
print('%2d -> ' % item, lists3)
打印如下:
14 -> [14]
1 -> [1, 14]
17 -> [1, 14, 17]
18 -> [1, 14, 17, 18]
16 -> [1, 14, 16, 17, 18]
11 -> [1, 11, 14, 16, 17, 18]
4 -> [1, 4, 11, 14, 16, 17, 18]
可以清楚的看到每次插入元素都可以保持序列的升序
总结
目前所提到的内容都不仅仅是对列表或者元组有效,还可以应用于几乎
所有的序列类型上。
而如果你只需要处理数字列表的话,数组可能是个更好的选择。(见下一节)
上一篇: 一致性哈希算法-源码篇
下一篇: 一致性哈希java实现算法