Python
競技プログラミング

Pythonで二分探索する公式ライブラリ

More than 1 year has passed since last update.

こんにちは。shamojiです。

相も変わらず、覚えたことはメモしていきたいので

発見したことをまとめていきたいと思います。


Pythonで二分探索法してくれるライブラリ

まずコードから


nibutan.py

import bisect

a=[1,3,5,7,9,11,13,15,17,19]
x=4

insert_index = bisect.bisect_left(a,x)

"""
insert_index=2
"""

a.insert(insert_index,x)

print(a)
"""
Out[1]:[1,3,4,5,7,9,11,13,15,17,19]
"""


見て分かるかと思いますが、bisect_leftメソッドは昇順ソートされたリストに昇順を崩さず挿入できる位置を返します。 

リスト要素が全部わかってないと使えない。

ただ$O(\log_{2} N)$でやってくれるからうれしい


その他メソッド

a=[1,1,1,1,2,2,2,2,3,3,3,3]

x=2

のような時に他のメソッドはどういう挙動をするのか調査してみた


example.py

import bisect

bisect.bisect_left(a,x)
"""
Out[1]: 4
[1,1,1,1,2,2,2,2,3,3,3,3]
^
"""

bisect.bisect_right(a,x)
bisect.bisect(a,x)
"""
Out[2]: 8
[1,1,1,1,2,2,2,2,3,3,3,3]
^
"""

bisect.insert_left(a,x)
"""
[1,1,1,1,2,2,2,2,2,3,3,3,3]
^
"""

bisect.insert_right(a,x)
bisect.insert(a,x)
"""
[1,1,1,1,2,2,2,2,2,3,3,3,3]
^
"""



使いどころさん

list要素数Nが$1<N<10^9$とかってめちゃくちゃなリストの中からランダムでアクセス要求があったりした場合は自前実装よりもライブラリを使用した方が早いしミスがないのでお勧めです。

ただし、insertは$O(N)$とくそ重いのでinsert_left か right 使うときは二分探索に関係なく$O(N)$スピードになるので要注意です。

それに、競技プログラミングにおいては、速攻で実装し問題を崩すことができるので、余計な実装時間を削れることでしょう。