阿里面试题:要求不用数学库，求 sqrt(2)精确到小数点后 10位

面试的考察点

1. 基础算法的灵活应用能力（二分法学过数据结构的同学都知道，但不一定往这个方向考虑；如果学过数值计算的同学，应该还要能想到牛顿迭代法并解释清楚）
2. 退出条件设计

解决办法

1. 已知 sqrt(2)约等于 1.414，那么就可以在(1.4, 1.5)区间做二分查找，如：

• 1. right=>1.5
• 2. left=>1.4
• 3. mid => (right+left)/2=1.45
• 4. 1.45*1.45>2 ?right=>1.45 : left=> 1.45
• 5. 循环从第3步开始

2. 退出条件

前后两次的差值的绝对值<=0.0000000001, 则可退出

const double EPSINON = 0.0000000001;
double sqrt2( ){
    double l = 1.4, r = 1.5;
    double mid = (l + r) >> 1;
    while (r - l > EPSINON){
        //如果值大于2，则移动右边界到mid，否则移动左边界到mid
        if (mid*mid > 2){
            r = mid;
        }else{
            l = mid;
        } 
        mid = (r + l) >> 1;
    } 
    return mid;
}