题解 | 平方根

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求非负整数 n 的平方根
     * @param n int整型 你需要求 n 的平方根
     * @return double浮点型
     */
    double findSqrt(int n) {
        /*
        //牛顿迭代法
        if(n==0) return 0.0;

        double x=n; //初始化猜测值
        double epsilon = 1e-7;  //精度要求比1e-5更严格一些

        while(true)
        {
            double next_x = (x+n / x) / 2.0;
            if(abs(next_x - x) < epsilon)
            {
                return next_x;
            }
            x = next_x;
        }
        */

        //二分查找
        if(n ==0 ) return 0.0;
        if(n==1) return 1.0;

        double left = 0.0,right = n;
        double epsilon = 1e-7;

        //对于大于1的数，平方根不会超过n/2+1
        if(n>1)
        {
            right = n/2.0 + 1;
        }

        while(right - left > epsilon)
        {
            double mid = left+(right - left) /2.0;
            double square = mid*mid;

            if(abs(square-n)<epsilon)
            {
                return mid;
            }
            else if(square<n)
            {
                left = mid;
            }
            else 
            {
                right = mid;
            }
        }

        return left+(right-left) / 2.0;

    }
};