pythonのbisectの使い方
binary searchをするライブラリ- これらを便利にラップしたものが、/python-sortedcontainers/
具体例
基本(bisect_left, bisect_right)
import bisect
import random
l = random.sample(list(range(0, 10**5)), 10**4)
random.shuffle(l)
"""
- bisect_left
- sortされたlistで左から探して挿入できる点を探す
- bisect_right
- sortされたlistで右から探して挿入できる点を探す
"""
l.sort()
for th in random.sample(list(range(0, 10**5)), 100):
idx = bisect.bisect_left(l, th)
print(f'idx={idx}, th={th}, prev_value={l[idx]}' )
挿入(insort_left)
binary searchを行って値も挿入するbisect_left+insertよりわずかに効率がいい
sortedcontainersのSortedListと同等の機能を実装できる
sl = [1, 3, 5]
bisect.insort_left(sl, 4)
print(sl) # [1, 3, 4, 5]