ホーム > libalgo

二分探索

概要

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

計算量

定数回のループを回すのが安定.ビットの数だけ回せば十分な気がするが未検証.余裕があれば 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;
}