题目描述

给定一个浮点数n，求它的三次方根。

输入格式
共一行，包含一个浮点数n。

输出格式
共一行，包含一个浮点数，表示问题的解。

注意，结果保留6位小数。

数据范围
−10000≤n≤10000

样例

输入样例：
1000.00
输出样例：
10.000000

算法1

(二分查找) $O(logn)$

C++ 代码

#include<iostream>
using namespace std;

double binarySearch(double left,double right,double n) {
    while(right-left>1e-8) {
        double mid=(left+right)/2;
        double cur=mid*mid*mid;
        if(cur<n) {
            left=mid;
        }
        else {
            right=mid;
        }
    }
    return left;
}
int main() {
    double n;
    cin>>n;
    double res=binarySearch(-100,100,n);
    printf("%0.6lf\n",res);
    return 0;

}

以前学二分的时候，觉得很简单，恩就是分一半丢掉。
然后把二分求解变成了两种情况，还记得当时看别人的代码一直纠结到底left>right,还是left>=right。
在查找数的时候做法是这样的。。先看等于，再看小于，再看大于。
mmmm。。。如果重复数怎么办，傻傻遍历啊。
从来没有理解到这个性质的问题，现在的理解是
在实现的时候我们一直是在选择一个区间，而区间要一直保持左端点和右端点的颜色是不同的。如同夹逼定理，
一直使选择的区间满足这样的性质，然后区间的长度不停的减小，直到为1，
这样自然就可以找到对应这个性质的端点即两个不同性质的分割点。

将等于的情况和小于或者大于融合起来，这才是二分。恩。。原来总是把等于额外考虑。时刻记得二分！