二分探索

left = inf
right = sup
while (right - left > 1) 
    mid = left + (right - left) / 2
    if judge(mid) == true
	    left = mid // 逆かも
    else
	    right = mid

ポイント

• 書く前に考察を詰め切る
  • 求めたいのは境界の左か右か
  • judgeをtrueにすべきなのはどっちか
  • 自分はめぐる式二分探索で脳死しようとするとコードが破綻する人間であることを思い出せ（それなりの思考リソースを割かないといけない)
• 切り捨て、切り上げに注意する
  • subする前にinfやsupが解となるケースを試す
  • supは切り捨ての関係上+1になるのかな？
• judgeはmid以下・以上でokかと考える
  • 丁度midでokかと考えるとうまく立式できないケースが多い

単調性を見出すコツ、二分探索が使える問題

• 「最大値の最小・最小値の最大を求めよ」
• 「OOが可能な値な最小・最大を求めよ」
• Z型のグラフ(あるところまでfalse, あるところからずっとtrue)が見える
• 考察の結果が一次関数
• ABC-CDの最大・最小問題は二分探索・尺取り・DP(貪欲)・愚直高速化のどれかであることが殆ど
  • 勿論例外もあるけど・・・(簡単な自明な上界とか)
  • 尺取りは二分探索でもできる
    • ただ、自分は尺取りのほうが得意なのを思い出しておく
• judgeはmid以下・以上でokかと考える
  • 丁度midでokかと考えるとうまく立式できないケースが多い

決め打ち二分探索を使わなくて良いもの

• 不等式を満たす最小・最大のx
  • それ割り算でよくないすか。と一旦足踏みする