586.对x开根II

描述

实现 double sqrt(double x) 并且 x >= 0。
计算并返回x开根后的值。

注意事项

你不需要在意结果的精确度，我们会帮你输出结果。

样例

给出 n = 2 ,返回 1.41421356

代码

1.二分法

public class Solution {
    /**
     * @param x a double
     * @return the square root of x
     */
    public double sqrt(double x) {
        double left = 0.0;
        double right = x;
        double eps = 1e-10;

        // 因为小于1的小数的平方是小于它本身的
        // 即小于1的小数的平方根大于该数本身
        // 如果不使right = 1则无法用二分法找到该数
        if (right < 1.0) {
            right = 1.0;
        }

        while (right - left > eps) {
            // 二分浮点数 和二分整数不同
            // 一般都有一个精度的要求 譬如这题就是要求小数点后八位
            // 也就是只要我们二分的结果达到了这个精度的要求就可以
            // 所以 需要让 right 和 left 小于一个我们事先设定好的精度值 eps
            // 一般eps的设定1e-8,因为这题的要求是到1e-8,所以我把精度调到了1e-10
            // 和-8差两位，开完平方结果差一位，结果是9位小数，取8位不会出现误差
            // 最后 选择 left 或 right 作为一个结果即可 
            double mid = left + (right - left) / 2;
            if (mid * mid < x) {
                left = mid;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

2: 牛顿法

public class Solution {
    /**
     * @param x a double
     * @return the square root of x
     */
    public double sqrt(double x) {
        double res = 1.0;
        double eps = 1e-12;

        while(Math.abs(res * res - x) > eps) {
            res = (res + x / res) / 2;
        }

        return res;
    }
}

详解：
f(x) = x - n ^ 2,转化为求f(x)的零点
http://blog.csdn.net/hyc__/article/details/41117009