趣味で競プロをやるようになり、Atcoderの問題を何問か解いているのだが、
やっている内に覚えないといけないこともいくつかあるわけで。
その内の一つに二分探索というアルゴリズムを使うという場面を多く見てきたため、自分が今よく利用しているpythonでいつでも使えるように二分探索を行うスクリプトでも書いておこうかと思った。
しかし取り掛かろうとして調べて見たところ、なんとpythonには二分探索を行うライブラリが最初から用意されているらしい。
それがこの「bisect」というもので、このライブラリについて調べて見た。
bisect
bisectモジュールのbisect関数はリストと値を入力とし、値をリストに挿入する位置のインデックスを返す。
とりあえずは使用例ということで、bisectを使ってみた。
>>> import bisect
>>> a=[10,20,30,40,50,60,70,80,90,100]
>>>
>>> bisect.bisect(a,55)
5
>>>
この例の場合、リストaに値55を入れようとした時、a[5](50と60の間)に入れるのが適切なため、５を返す。
ちなみにbisectを使う時、入力するリストはすでにソート済みであることが前提である（これは本来の二分探索でも同じである）。ソートされてないリストを入力してもエラーは発生しないが、間違った形で二分探索が行われてしまう。
>>> import bisect
>>> a=[54,32,76,33,89,44,323,67,88,1]
>>> bisect.bisect(a,55) # ソートしなくても二分探索は行うが・・・
6
bisect_leftとbisect_right
また、入力した値が既にリストに入っていた場合、リストでその値の前に入れるか、後に入れるかで使い分けたいという場合もあると思う。この場合どうすれば良いのか？
bisectモジュールには更にbisect_leftとbisect_rightという関数があり、各々の場合に応じてこれらを使い分ける。
使用例を示す。
>>> import bisect
>>> a=[1,2,2,2,3]
>>>
>>> bisect.bisect_left(a,2)
1
>>> bisect.bisect_right(a,2)
4
>>> bisect.bisect(a,2)
4
この例の場合、a[1]からa[3]まで2であり、bisect_leftで2をリストaに適用すると、挿入点は2の一番前の位置である1を返す。
bisect_rightを使った場合はその逆で、挿入点は2の一番後の位置である4を返す。
ちなみにbisect関数はbisect_rightと同じ動作をする。
insort
insort関数はbisect関数の動作に加えて、リストへの挿入も行う関数である。
bisect関数と同様に、リストに入力と同じ値があった場合にその値の前か後のどちらに挿入するかは、insort_leftとinsort_rightという関数があるので使い分ける。
ちなみにinsort関数はinsort_rightと同じ動作をする。
>>> import bisect
>>> a=[10,20,30,40,50,60,70,80,90,100]
>>> a
[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
>>>
>>> bisect.insort(a,55)
>>> a
[10, 20, 30, 40, 50, 55, 60, 70, 80, 90, 100]
>>>
今後二分探索を利用する機会があったら活用していきたい。
（でも、できればライブラリ頼りではなく、本当はアルゴリズム自体も自分で理解して、一から書けるようにすべきだけど・・ね）