python bisect

pythonのbisectの使い方

タグ bisect

pythonのbisectの使い方

具体例

基本(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]

参考