【Python】二分探索を行うbisectの関数の挙動について
この記事では、Pythonで二分探索を行うbisectライブラリについて記載します。
そもそも二分探索とは
二分探索については以下の記事がわかりやすいです。
ざっくりまとめると、以下のような感じです。
- 数字がn個入ったリストRの中から、xを見つけ出したい
- まともに検索すると、Rを最初から最後まで全部確認しないといけない
- ここで、Rが昇順に整列しているとする
- Rの真ん中の数字がxより小さいならRの前半、xより大きいならRの後半にxが存在する（探す範囲を一気に1/2にできる）
- 半分になったRについても真ん中をxと比較してどんどん半分に絞りこんでいく
こんな感じです。
普通にやると、O(n) の計算量がかかる検索を O(log n) でできるようになります。
この二分探索について、Pythonではbisectというライブラリをインポートすることで自分で実装せずに使えるようになります。
が、ちょっとトリッキーな挙動で、公式リファレンスを読んでも分かりにくいのでまとめてみました。
bisect関数の挙動
bisect関数は bisect(R: リスト, x: 検索したい数) みたいな感じで使います。
戻り値が結構独特で、「R に x を辞書順で挿入すべき位置を戻す」という仕様になっています。
つまり、Rにxが含まれていようがいまいが何かしら値が戻ってくる関数になっています。
詳細は以下のサンプルコードを読んでみてもらうと早いのですが、x を挿入できる位置の戻し方よって2つの関数があります。
- 左側の位置を戻す bisect_left 関数
- 右側の位置を戻す bisect_right 関数 ※名前を省略して bisect 関数としても良い
とにかく、以下のサンプルコードをご覧ください。
import bisect a=[1,2,2,2,3,6] print(bisect.bisect_left(a, 1)) # 0が戻り値 print(bisect.bisect_left(a, 4)) # 5が戻り値 print(bisect.bisect_left(a, 7)) # 6が戻り値 print(bisect.bisect_left(a, 2)) # 1が戻り値 print(bisect.bisect_right(a, 2)) # 4が戻り値 print(bisect.bisect_right(a, 4)) # 5が戻り値 print(bisect.bisect_right(a, 7)) # 6が戻り値
戻り値については、リストのスライス記法と同じで a=[1,2,2,2,3,6] の中で【2を挿入できる場所】にある , が左から何番目のものかを戻す。みたいな覚え方をしています。
leftだったら1つ目の , なので 1 を、rightだったら4つ目の , なので 4を戻す感じです。
別の捉え方として、以下の考え方も使う機会がそこそこありそうです。
- bisect_left(R, x) : リストRに含まれるx未満の数値の個数
- bisect_right(R, x): リストRに含まれるx以下の数値の個数
こんな感じで結構独特なので、例えばリストにxが含まれているかどうかを知りたい時には少し工夫をする必要があります。
例えば、以下のような形で使うことが多いのかなぁと思います。
import bisect a=[1,2,2,2,3,6] # xがaに含まれているかを確認したい x = 2 i = bisect.bisect(a, x) if a[i - 1] == x: print("Yes") else: print("No") x = 5 i = bisect.bisect(a, x) if a[i - 1] == x: print("Yes") else: print("No") # x以上の数字がaに含まれているかどうかを確認したい x = 7 i = bisect.bisect(a, x) if i == len(a): print("Yes") else: print("No") x = 2 i = bisect.bisect(a, x) if i == len(a): print("Yes") else: print("No")
ちなみに、bisect.bisect_right と bisect.bisect は以下のように常に同じ挙動をします。
可読性を気にせず、自分だけで使う分にはbisect_right を使う必要はないですね。
import bisect a=[1,2,2,2,3] print(bisect.bisect_right(a, 2)) # 4が戻り値 print(bisect.bisect_right(a, 4)) # 5が戻り値 print(bisect.bisect(a, 2)) # 4が戻り値 print(bisect.bisect(a, 4)) # 5が戻り値
どんな時に二分探索を使う？
さて、ここまで紹介してきた二分探索の bisect 関数ですが、Rが整列されていない場合は一度整列する必要があります。
整列の計算量は一般に O(n) なので、一見わざわざ整列してまで使う意味がないように感じます。
が、例えば検索したいxをn通り試したい場合だとO(n^2) かかるところを、事前に整列しておくことで O(n * log n) で計算できます。
※nが大きい場合、事前の整列にかかる計算量 O(n) を考えても早く計算できる
具体的には、以下の記事の最後の問題で使ったりします。
ということで、本日は二分探索についての記事でした。
それでは〜。
