答えで二分探索 — pres1dent.net

判定問題への変換

候補値 $x$ に対する判定 ok(x) が単調なら、真偽の境界を二分探索できる。「最大値を最小化」「最小値を最大化」という形で頻出する。

long long ng = -1;
long long ok = 1LL << 60;
while (abs(ok - ng) > 1) {
    long long mid = ng + (ok - ng) / 2;
    (check(mid) ? ok : ng) = mid;
}