Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

二分探索の本質を考える

二分探索について頭を整理します。

二分探索の応用事例

  • ソートされた列から最小値を探す
  • 半分全列挙の相方を探す
  • あるxについて成り立つか問いを設定して(貪欲に計算出来ることが多い)、問題条件にあったxを探す

二分探索とは?問い系の二分探索が本質

問い系の二分探索をグラフ考えてみると、

f:id:akiradeveloper529:20190731174047j:plain

問いを返り値をTFとした関数とみて、それが広義単調であるということが条件とわかる。

つまり、配列がFFFFFTTTTTTTだったり、TTTTTTTTFFFFFFFだったりすることが条件となる。

例えば、 E - 引きこもり では、グラフの大きさをインデックスにして、その個数を値にした配列を考えて、「値が0より大きくなったところの最初のインデックス」が最小のqであると考えているが、これは、配列の要素が全部正であることを考えると累積和は必ず広義単調増加しているため、そのインデックスを探すのに二分探索が適用可能になるというのが別解として乗っている。想定のしゃくとり法でもいいと思うが、自分としてはに累積和から二分探索の方が自然かなと思った。この場合、配列はFFFFFFTTTTTTのような形になってると考えることが出来る。このように、累積和と二分探索は相性が良いケースが多く見られる。(これはそもそも論として、しゃくとり法も二分探索が要求しているような性質に依存していることから別解が存在しただけに思えるが、ぼんやりとしているので、理解が進んだら別途記事にする予定)

いわゆる、値を探すだけの二分探索(lower_boudみたいな)に話を戻す。これも値を探すとは言っているが、結局問い系の二分探索に帰着出来る。つまり、1233445という数列があり、これに対して4を探すと行った場合、4以上かそうでないか(ローランドかローランド以外かみたいな感じで)の問いを考えて、FFFFTTTとする。こうすると、問い系の二分探索に帰着出来る。

値ではなくTFが広義単調であることが条件だと考えると、問い系の二分探索も自然に見えてくる。

二分探索の実装方法

二分探索は素で実装することが多いため、定型文として実装出来るようになっておく方がいい。

[a,b)を探索区間として二分探索するとき、lb=a-1, ub=bとして、ub-lb>1の間だけループするというのがわかりやすいと思った。>1は、無限ループしないために存在する。例えば>0にすると無限ループするでしょう。なので、浮動小数点で実行する場合は、十分に小さい値epsを設定して代わりに使う。

しかし、Rustでは仮にaが0の時はlbの初期値がマイナスになってしまい、整数型の問題に苦しめられることになる。インデックスとして使う整数値がusizeしか認められていないことが問題で、負値も認めてくれよというフィードバックもあるようだが、認められるようになるとはとても思えないので、受け入れるしかない。Rustはその他にも、競プロでは最善と言い難いことがたまにある。