～探索
- 二分探索は単調変化する関数に対して、YES/NOの境目を見つける探索 参考
- 三分探索は凸関数である関数に対して、最大値・最小値を見つける探索 参考1 参考2
- 二分探索・三分探索は気がつくまでが長い。単調性が無いかというのは常に考えておく
- 「最大値の最小化」
- リアクティブ問題と二分探索は相性がいい
- 二分探索+全探索の高速化の話 ここ ここも
- 【テク1】答えを二分探索で固定すると、x以上とx未満で0,1（または-1,1）になってうまく扱えるというテクがある（中央値と絡めてよく使う）
- 【テク2】「ある条件でソートしたときのK番目の数を求めよ」というのは、答えの数で二分探索するというものがある
- 【テク3】平均値っぽい分数最大化は二分探索
- 二分探索から単調性を引いたもの『二分法』
- 単調性がなくても、場合によっては境界を二分法で探すことができる
- 中央値の定理？
- 二分探索と区別するために便宜上二分法と言っているが、ほんとに言い方正しいか分かってない
問題
二分探索(実数)
- yukicoder No.67 よくある棒を切る問題 (1)
- JOI ski - スキー (Ski) 解説1 解説2
- CF532 NN and the Optical Illusion 解説
- 【テク3】ABC034D 食塩水
- 【テク3】AC おまかせ 解説
二分探索(整数)
- CSA55 Build the Fence 解説
- yukicoder No.168 ものさし
- yukicoder No.507 ゲーム大会(チーム決め)
- yukicoder No.648 お や す み 解説
- CF Too Easy Problems
- ECR27 Fire in the City
- 【テク2】ABC123 Cake 123 解説
- ECR32 K-Dominant Character
- ARC088 Christmas Tree 解説 （二分探索in二分探索）
- AC Maxmin Tour
- yukicoder No.702 中央値を求めよ LIMITED 解説
- 【テク1】ARC101 Median of Medians 解説
- 【テク1】【テク2】AOJ L番目のK番目の数 (LthKthNumber) 解説
- 【テク1】AGC006 Median Pyramid Hard
- HR Picu Bank
- AC Come Together 解説
- AC Snuke the Wizard 解説
- yukicoder No.814 ジジ抜き 解説
- 【テク2】yukicoder No.817 Coin donation 解説
三分探索
- yukicoder No.306 さいたま2008 (実数で最小値)
- yukicoder No.198 キャンディー・ボックス２ (整数で最小値)
- CodeChef Calculator (整数の最大値)
- HOJ Treasure Hunt（実数で最小値） 解説
- CF320 Weakness and Poorness (実数で最小値) 解説
- CSA73 Ricocheting Balls（整数で最小値）解説
- AOJ ヒバラ海に沈む遺跡 解説（実数で最大値）
二分法
【発展的話題】並列二分探索
- Parallel Binary Search 解説(英語)
- 複数の二分探索を1つに纏めるテクであるが、二分探索を纏めるというよりかは二分探索で同じような計算が沢山出てくるのでそれを1回に減らして二分探索していこうというモチベーション
- 永続化で対応できる場合もあるらしい
- 問題
- AGC002 Stamp Rally 解説1 解説2
- HR Selective Additions 解説
- AC Union Sets
