- はじめに
- めぐる式二分探索のメリットと参考文献
- コピペ用
- 例題
はじめに
AtCoderで二分探索を実装するときバグらせないように考えると結構時間かかりませんか?自分はかかります。
競技プログラミング界隈ではめぐる式二分探索という二分探索の書き方(流派?)があり、使いやすい、バグりにくくなど様々なメリットがあります。
Python実装を公開しているブログはパット見、見つからなかったのでおいておきます。使用例もおいておきます。
めぐる式二分探索のメリットと参考文献
めぐる式二分探索を使うメリットとして以下があげられます。
- 配列化できない関数を探索可能 (bisectモジュールでは不可)
- バグりにくい (終了状態がきちんとしている)
- ライブラリとして扱うことが可能で実装が高速化される
- 思考リソースの消耗を防げる (条件を満たすかそうでないかだけ考えれば良い)