はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける二分探索・三分探索問題まとめ [二分法]

~探索

  • 二分探索は単調変化する関数に対して、YES/NOの境目を見つける探索 参考
  • 三分探索は凸関数である関数に対して、最大値・最小値を見つける探索 参考1 参考2
  • 二分探索・三分探索は気がつくまでが長い。単調性が無いかというのは常に考えておく
  • 「最大値の最小化」
  • リアクティブ問題と二分探索は相性がいい
  • 二分探索+全探索の高速化の話 ここ ここも
  • 【テク1】答えを二分探索で固定すると、x以上とx未満で0,1(または-1,1)になってうまく扱えるというテクがある(中央値と絡めてよく使う)
  • 【テク2】「ある条件でソートしたときのK番目の数を求めよ」というのは、答えの数で二分探索するというものがある
  • 【テク3】平均値っぽい分数最大化は二分探索
  • 二分探索から単調性を引いたもの『二分法』
    • 単調性がなくても、場合によっては境界を二分法で探すことができる
    • 中央値の定理?
    • 二分探索と区別するために便宜上二分法と言っているが、ほんとに言い方正しいか分かってない

【発展的話題】並列二分探索