競技プログラミングにおける二分探索の関数の使い方を忘れがちなので備忘録として残しておきます。
また、この記事では二分探索がどのようなものかについては扱っておりませんのでご注意ください。
さらに、この記事は基本的な使い方を確認することが目的なのでご了承ください。
#Pythonでの二分探索(bisectモジュール)
Pythonではbisectモジュールで二分探索に関連した関数が扱われています。
このモジュールでは、(昇順)ソート済みのリストの順序を保ちながら操作することをサポートしています。
競技プログラミングでは、下記の二つの関数を主に用います。
また、以下では調べたい要素をx,調べる**(昇順)ソート済みのリスト**をaとし、第一引数はa,第二引数はxとします。
第三引数,第四引数ではaの中での調べる範囲を指定できますが、ここでは扱いません。bisectモジュールを見てください。
###①bisect_left
(順序を保ったままで)xのうちで一番左側のaへの挿入箇所のインデックスが返されます。
$\leftrightarrow$x以上の要素で最小の要素のインデックスが返されます。
$\leftrightarrow$左隣の要素はxより小さい要素の中で最も(インデックスが)大きい要素になります。
###②bisect_right
(順序を保ったままで)xのうちで一番右側のaへの挿入箇所のインデックスが返されます。
$\leftrightarrow$xより大きい要素で最小の要素のインデックスが返されます。
$\leftrightarrow$左隣の要素はx以下の要素の中で最も(インデックスが)大きい要素になります。
#C++での二分探索(lower_boundとupper_bound)
C++ではalgorithmライブラリで二分探索に関連した関数が扱われています。
このライブラリでは、アルゴリズムの要件を満たすイテレータを持つ場合はどのデータ構造でも動作します。
競技プログラミングでは、下記の二つの関数を主に用います。
また、先ほどと同様に、調べたい要素をx,調べる**(昇順)ソート済みの配列**をaとします。
この時、第一引数をa.begin(),第二引数をa.end()として調べる範囲を指定し、第三引数に調べたい要素であるxを指定します。
###①lower_bound
Pythonのbisect_leftと同義ですが、x以上の要素で最小の要素のイテレータが返されます。
また、最小のインデックスを得たい場合は(戻り値)-a.begin()で得ることができます。
###②upper_bound
Pythonのbisect_rightと同義ですが、xより大きい要素で最小の要素のイテレータが返されます。
また、最小のインデックスを得たい場合は(戻り値)-a.begin()で得ることができます。
#おまけ
✳︎昇順ソート済みのリストであることが必要ですが、演算子のオーバーロードにより昇順でないソートが可能です。
✳︎C++のlower_bound,upper_boundについて詳しく知りたい場合は、この記事を参考にしてください。
✳︎他にも重要なことがあったらコメントなどで教えてください！