こんにちは。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)$スピードになるので要注意です。
それに、競技プログラミングにおいては、速攻で実装し問題を崩すことができるので、余計な実装時間を削れることでしょう。