二分探索

概要

条件を満たす/満たさないの境界を求める．

計算量

定数回のループを回すのが安定．ビットの数だけ回せば十分な気がするが未検証．余裕があれば 100 回くらい回しておく．

実装

// check = true となる最大の値を探索する
template <class Function>
double binarySearch(double lb, double ub, Function check) {
    assert(lb <= ub);
    double d = ub - lb;
    for (int i = 0; i < 100; i++) {
        d /= 2;
        if (check(lb + d)) lb += d;
    }
    return lb;
}