ホーム > libalgo

二分法

実装

ld bisection_method(ld x0, ld x1, std::function<ld(ld)> f) {
    ld y0 = f(x0), y1 = f(x1), m;
    int s0 = std::abs(y0) < eps ? 0 : y0 < 0 ? -1 : 1;
    int s1 = std::abs(y1) < eps ? 0 : y1 < 0 ? -1 : 1;
    assert(s0 * s1 <= 0);
    if (y0 > y1) std::swap(x0, x1);
    for (int i = 0; i < 200; i++) {
        m = (x0 + x1) / 2;
        if (f(m) > 0)
            x1 = m;
        else
            x0 = m;
    }
    return m;
}

検証

AOJ 2220 (Submission)