给刚刚学习二分的同学讲解一下,为什么这题使用二分?
1.单调性
题目对应数学函数为f(x) = x^3,该函数在整个作用域范围内为单调递增。
那么,如果中间值的 3 次方小于目标值,那么答案肯定在中间值左侧区间;反之,则肯定在右侧区间。
据此,我们可以通过比较中间值的 3 次方和目标值来决定搜索的方向。
2.有界性
对于正数,它的 3 次方根一定在 0 到它本身之间。
对于负数,它的 3 次方根一定在它本身到 0 之间。这为二分查找提供了明确的搜索范围。
3.高效性
二分法通过不断缩小搜索范围,每次将搜索空间减半,因此可以快速收敛,逼近答案范围。
相比于其他方法,二分法通常具有更好的时间复杂度,尤其在需要高精度计算时表现更为出色。
4.精度问题
答案范围是浮点数构成的序列,我们在求解三次方根的时候(尤其这个三次方根不是整数的时候),其解一定是浮点数。
考虑到浮点数的精度问题,我们难以使用枚举或者搜索来控制小数位后规律变化,同样也就难以实现将每一种情况都完全遍历。
那么我们使用合法范围的数据不断尝试逼近目标值,当查找范围内任意两点达到我们设置的误差值内时,即认为找到解。
以上!我们选择二分比较合理高效。
核心代码
1.确定二分范围
记n变量代表目标值
当 ,查找范围在 之间
当 ,查找范围在 之间
if (n > 0)
l = 0, r = n;
else
l = n, r = 0;
2.check 函数
检查中间值,与目标值之间的关系,并对应收敛范围。
bool check(double x) {
return x*x*x > n;
}
3.二分模板
进入二分的条件:左右边界差尚未达到误差值
进入二分后:
检查 mid 是否满足上述查找需求,根据返回值划分左右区域并收敛一半。
注意:移动左右边界时,无法像整数的形式一样加 1 或者减 1,那么我们就移动到 mid 位置即可。
while (r-l >= 1e-8) { //开始二分
mid = (l+r)/2; //求中间值
if (check(mid)) { //判断答案满足要求
r = mid; //移动右边界
} else { //此时,中间值3次方<=当前目标值,那么左端点也可能为答案
l = mid, ans = l; //移动左边界并记录答案
}
}
接下来只需要补全代码完成输入输出即可。
共 5 条回复
好的 多谢啦
我帮你把这个改到题解区哈~
@root 多谢站长指导哈哈
数字,字母和汉字之间加空格
写的很好啊,赵老师