個人的三分探索のテンプレメモ

二分探索の問題を解いていたら、凸グラフの頂点を求めたくなって、ついでに三分探索の練習したのでメモ。問題は以下。

三分探索詳しい説明は以下のサイトを参考に（というかほぼそのまま実装）した。

今回は整数のみの練習で、実数は扱ってない。

テンプレ

添字で混乱しないように、参考サイトから名前を変更してある

  // 3分探索で最も大きい本数を求める (グラフは上に凸)
  ll lo = LO_INIT;
  ll hi = HI_INIT;
  while (abs(lo - hi) > 2) {
    ll cl = (lo * 2 + hi) / 3;
    ll ch = (lo + hi * 2) / 3;
    if (f(cl) > f(ch)) {
      hi = ch;
    } else {
      lo = cl;
    }
  }

  // lo, lo+1, hi の3つのいずれかが求めたい値
  ll ans = 0;
  rep(i, lo, hi + 1) ans = max(ans, f(i));
  cout << ans << endl;