小数二分【基于整数二分思想】

1. 数的三次方根 - AcWing题库

小数二分的思想其实比较简单，与整数二分差别基本上只在

left

和

right

的取值范围

例如，在这个题中

 -10000 <= n <= 10000

所以我们就直接将

• left = -10000
• right = 10000

代码模板

#include<iostream>usingnamespace std;intmain(){double x =0;
    cin >> x;double mid ;double l =-10000, r =10000;while(r - l >=1e-8){
        mid =(l + r )/2;if(mid * mid * mid >= x) r = mid;else l = mid;}printf("%f",mid);return0;}

问题一：为什么不再需要+1，而是直接=mid？

因为这里涉及到的左边界 和 右边界都是小数，若是直接+1，则可能导致直接超出结果了！

问题二：为什么循环条件变了？

因为这里需要保留6位小数，一般情况下我们循环条件只需要

> 精读2位

即

6 + 2 = 8

，所以这里只需要当r 比 l大

1e-8

的时候就一直执行

问题三：为什么直接输出就行？不要%.6f控制？

因为这里double是默认保留6位输出的，所以我们就不需要自行控制了

问题四：这里的扩展性怎么样？

因为这里适合的题目是计算这个数字的三次方根，对应的判断是

mid * mid * mid 

。

那么同样的，如果我们需要计算四次方根，就只需要加上一个mid即可！

问题五：为什么这里就能想到使用二分进行查找呢？

在我们编程过程中，可能并没有一个比较专业的数学知识进行计算

三次方根

。

但是我们拥有计算机，计算机最忠诚的一点就是能忠诚的执行你的每一句话，所以我们就可以让他在一个范围内不断尝试，直到找到那一个数。

其实算法的本质就是进行

遍历

，你觉得很简单吗？但是很多情况下，我们的遍历可能会导致重复的，这可能会浪费很多时间，所以其实算法最终的目的是 无重复的进行遍历

所以，其实最终我们可以修改左右边界的，同样也能通过

double l =-100, r =100;