二分探索の終了条件
二分探索とは
二分探索 - Wikipedia
↑ こ↑こ↓に載ってる奴．昇順，降順といった制約を持っているものに対して非常に高速(O(logn))で処理できるアルゴリズムです．考え方自体はものすごいシンプルだけど，こんなのも実装できない自分が悔しい．
何が無理かというと，終了条件がよくわからない．low,mid,hiの3つがあるときどれが答えなの？いつ終了するの？結局low,mid,hiのどれを答えにすればいいの？という疑問
難しい問題になると，単体の知識問題が減って，こういう技を上手く合わせ技で使い必要があるので，ここらへんで文章書いて考えを整理したかった．前提として離散値で考えます(int,longの整数型)
パテいーん１． よくあるソート済み配列のうまくいく場合
midで見つかったときにそのままbreakしてmidを答えとして探索を終えればいいだけ．
これはちょろいね
パテいーん2の考察に詳細は譲るとして，hi > low+1 が成立している間まで探索を続けるといい感じ．
パテいーん２． よくありソート済み配列で答えが見つからない場合
(low,hi) = (奇数，偶数),(偶数,奇数)の場合について考える．
うまく見つからないと，hi = low+1となるような2つの要素による区間に収束する．このとき，遇，奇がどちらの場合でもmid = (hi+low)/2=lowとなるので，区間が2となるつまりhi > low+1 が成立している間まで探索を続けるといい．
パテいーん３． 競プロでの二分探索では一番頻出（だと思ってる）最大，最小の境界探索に使う
最初から，最後からの一個ずつの総当りがO(n)をかけるのに対して，O(logn)になるので，はやい．つよい ちょっと時間削ろうとなるとシンプルな割に強力な手法だからココらへんは迷わずサクサク実装できないとつらい．
俺が解いた，見たことあるやつだとこんなのがあった↓ 二分探索ができないと部分点まで突破できなかったりする．
------------------
Modular Query | Aizu Online Judge
集合内に1とM-1の間で割り切れる要素が一つでもあるかどうかを二分探索．クエリは一個一個逐次処理するしかない．
C: データ構造 - AtCoder Regular Contest 033 | AtCoder
AtCoder Regular Contest 033 解説 僕の解説より100倍詳しくて丁寧でつよい
概要としては，セグメント木のインデックスに二分探索していく感じ．
-------------------
実はこの記事はこういうパテいーんの終了条件をどうにかしたかっただけなのでよーく考える．たい
まずイメージとして0,1,2,…,k,...,n-1までのn個の要素があるとして条件Xを満たすのは，
0からkまでとなる問題があるとしてこの最大値のkを求めてねという問題とかで二分探索を使うことになる．
配列にすると，インデックスiについて，条件Xを満たす0,条件Xを満たさない1としてみると
000....0011....11（,は省略）というような配列で0が現れる最大のインデックスi_maxは？を求める問題だともいえる．(こう書いてみるとパテいーん1,2と共通点を感じるように思えてくる)
このとき，
[1] midで0となる→low =mid としていくことで，もっと攻めていく
[2] midが1となる→hi = mid としていくことで，もっと抑える
として二分探索を行うことになる．
初期条件に，lowには明らかに0となるインデックス，hiには明らかに1となるインデックスを初期値としておくと，最後はlowが条件を満たす0，hiが条件を満たさない1となる2つの要素の区間に収束する．条件を満たさない最小のインデックスも求まるじゃないか(憤慨)．このときに下線部の制約条件を守らないと上の太字のようには必ずしもならないので注意．
なぜこうなるかの思考実験↓
二分探索を行っていく間ではlow,hiの区間で含まれる0の個数がa，1の個数bが初期状態となるとして，この場合だと
[1]midで0をとった場合low,mid間の0を弾く，0,1の境界が残りつつ，aの値が減少
[2]midで1をとった場合mid,hi間の1を弾く，0,1の境界が残りつつ，bの値が減少
これを繰り返していくと，究極的にはlow,hi区間でのa,bがともに1となる状態に収束することになる．
本題の終了条件をパテいーん２．の時のように考えると，hi > low+1 が成立している間まで探索してhi = low+1となったときに終了して，条件を満たす最大値はlowを答えとして，条件を満たす最小値1(の最小のインデックスを求める問題)ならhiを答えとするといいということになる．
パテいーん３についてはこれを念頭において，下のように書くとよろしい！ コードスニペットに落としこんでもいいかもね
int low = 0;
int hi = max;
int mid = 0;
while(hi > low+1) // これがこの記事の答え
{
mid = (low+hi)/2;
if(条件Xを満たす(mid))
{
low =mid;
}
else
{
hi = mid;
}
}
パテいーん1,2については，条件Xを満たす(mid)内のブロックで return mid;
elseの方は空白
midをreturnできなければ，答えが見つからなかった旨をreturn -1;とかしてやるといい感じ
上級者の人たちだったらここらへんは思考タイム0なので慣れないと( ･`ω･´)
