一、算法简介
浮点数二分相比与整数二分就要简单很多了，但是还是要注意范围的问题。
以下给出一个小例子，求 \(x\) 的平方根，\(x\) 的范围在 \([0, 10000]\) 内：
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
double n;
cin >> n;
double l = 0, r = 10000;
while (fabs(l - r) > 1e-8)
{
double mid = (l + r) / 2;
if (mid * mid <= n) l = mid;
else r = mid;
}
printf("%.6lf", l);
return 0;
}
- 虽然没有下标问题，但是要注意初始的范围问题，比如 \(n\) 在 \([0, 1]\)之间，那么右区间 \(r\) 就不能取 \(n\) ，因为答案一定比 \(n\) 大。
- 一般情况下浮点二分会涉及到精度的问题，解决办法就是比输出结果多两位，就不会出问题，比如上面代码 \(while\) 中的\(10^{-8}\)，要求输出后六位，所以要高两位即可。
二、题目描述
给定一个浮点数 \(n\)，求它的三次方根。
输入格式
共一行，包含一个浮点数 \(n\)。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留 \(6\) 位小数。
数据范围
\(−10000≤n≤10000\)
输入样例：
1000.00
输出样例：
10.000000
三、原题链接
四、算法思路
- 设置\(double l = -10000, r = 10000\)，只需要找到 \(mid * mid * mid\) ≤ \(n\) 的最大值即可。
- 浮点二分相比于整数二分要简单很多。
五、源码
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
double n;
cin >> n;
double l = -10000, r = 10000;
while (fabs(l - r) > 1e-8)
{
double mid = (l + r) / 2;
if (mid * mid * mid <= n) l = mid;
else r = mid;
}
printf("%.6lf", l);
return 0;
}