double sqrt_binary(long long n, double epsilon = 1e-10) {
    if (n < 0) {
        throw invalid_argument("输入必须为非负整数");
    }

    if (n == 0 || n == 1) return n;

    // 阶段 1
    long long low = 1, high = n;
    long long k = 0;

    while (low <= high) {
        long long mid = (low + high) / 2;
        long long mid_sq = mid * mid;

        if (mid_sq == n) {
            return mid;
        } else if (mid_sq < n) {
            k = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    long long next_k = k + 1;
    if (next_k * next_k == n) {
        return next_k;
    }

    // 阶段 2
    double low_d = (double)k;
    double high_d = (double)(k + 1);
    double mid;

    while (high_d - low_d > epsilon) {
        mid = (low_d + high_d) / 2;
        double mid_sq = mid * mid;

        if (mid_sq < n) {
            low_d = mid;
        } else {
            high_d = mid;
        }
    }

    double result = (low_d + high_d) / 2;
    long long check_int = (long long)(result + 0.5);
    if (check_int * check_int == n) {
        return check_int;
    }

    return result;
}