代码模板-二分

bool check(int x);  // 判断 x 是否满足性质

int solve_r(int l, int r) {  // 找最后一个满足性质的点
    while (l < r) {
        int mid = (l + r + 1) >> 1; // 向上取整
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

int solve_l(int l, int r) {  // 找第一个满足性质的点
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

const double eps = 1e-8;

bool check(double x);

double solve(double l, double r) {
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    return l;
}

double solve(double l, double r) {
    for (int i = 0; i < 50; i++) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    return l;
}