GESP 2025年6月 C++五级 单选题 第12题

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;
}

• A. 「阶段1」的目标是寻找正整数 n 可能的正完全平方根
• B. 「阶段2」的目标是如果正整数 n 没有正完全平方根，则在可能产生完全平方根附近寻找带小数点的平方根
• C. 代码 check_int = (long long)(result + 0.5) 是检查因浮点误差是否为正完全平方根
• D. 阶段2的二分法中 high_d - low_d >= epsilon 不能用于浮点数比较，会进入死循环

正确答案：D