二分探索モジュール bisectの使い方
はじめに
今回は競技プログラミングでPythonを使っていたら、かなりの高頻度で使用するモジュール『bisect』を紹介していきたいと思います。内容は公式のドキュメントを参考にしています。
二分探索アルゴリズム
bisectは配列二分法アルゴリズムで、簡単に言うと「ある数字を配列に挿入する場合において、何番目の大きさの値であるか」を算出することが出来ます。bisectを使わない場合、
1. 配列をソートする。
2. 数字をソートした配列の要素と前から比べていき、大きくなったところで処理を終了する。
といった流れになります。
ここで 2について考えていきたいです。
ここで説明している 2は「線形探索」と呼ばれるアルゴリズムです。もしも一番初めの要素より挿入する要素が小さければ１回で探索は終わります。しかし一番最後の要素よりも大きかった場合は、その配列の長さと同じだけ探索を行う必要があります。ここで配列の要素数をNとおくと、探索を行う平均回数は1/2 * Nと考えられます。つまり計算回数はNに比例するといえます。これをO(N)と表すことが出来ます。
線形探索よりも性能の良い挿入のアルゴリズムが「二分探索」です。先に計算量から説明すると、このアルゴリズムはO(log N)と表すことが出来ます。logNとNとの間の関係は以下の図で表される通りで、Nが大きくなるにしたがって差は広がっていきます。
アルゴリズムの流れを説明します。
- 配列の数字の真ん中の数字を見つける。
- その数と挿入する数を比較して、小さければ真ん中より前、大きければ真ん中より後ろの配列を次の探索範囲にする。
- 2を分割できなくなるまで行う。
結構シンプルな考えです。探索範囲が、Nの半分→Nの半分の半分→Nの半分の半分の半分というように小さくなっているので、線形探索よりも効率的なのがよくわかると思います。
計算量がlogNになる証明は以下のようになります。
分割を行う回数をsと置くと、最後に残る要素数は1であるため、
N/2s = 1
つまり
N = 2s
であり、底が 2の対数をとると、
s = log2(N)
となります。
bisectの使い方
ここからはコードを中心にbisectモジュールの使い方を解説していきます。
bisect_leftとbisect_rightがありますが、異なる点は、「リストの中に挿入する数字と同じ要素があった場合、それらの中で一番前（左）に挿入するか、後ろ（右）に挿入するか」です。
# モジュールをインポート import bisect #サンプルのリスト sample_list = [3, 2, 3, 1, 6, 5, 2, 1, 5] #ソート sample_list = sorted(sample_list) #output -> [1, 1, 2, 2, 3, 3, 5, 5, 6] bisect.bisect_left(sample_list, 3) #output -> 4 bisect.bisect_right(sample_list, 3) #output -> 6
サンプルのリストを用意して動作の確認を行います。
まずソートを行って、２分探索の準備を行います。結果を出力してみると3が2つあることを覚えておいてください。
その後、bisect_leftとbisect_rightを使ってみます。
bisect_leftは3を、3の集合体の一番左に挿入しています。bisect_rightは右に挿入していることがわかります。これが2分探索を使って行われるので線形探索よりも高速です。
おわりに
今回はbisectモジュールについて解説していきました。
競プロでは頻出なので、存在だけでも覚えておきましょう。（細かい書式は覚えなくても調べればすぐにわかると思います。）
お疲れ様でした。
