LC-69

    public static int mySqrt(int x) {
        if (x == 1) {
            return 1;
        }
        int min = 0, max = x;
        while (max - min > 1) {
            int mid = (max + min) / 2;
            //用x/m<m而不是m*m>x防止溢出
            if (x / mid < mid)
                max = mid;
            else
                min = mid;
        }
        return min;
    }

LC-69

牛顿迭代

迭代公式: xi+1=xi - (xi2 - n) / (2xi) = xi - xi / 2 + n / (2xi) = xi / 2 + n / 2xi = (xi + n/xi) / 2。

有了迭代公式,程序就好写了。关于牛顿迭代法,可以参考wikipedia以及百度百科

或者使用二分查找: 对于一个非负数n,它的平方根不会小于大于(n/2+1)。在[0, n/2+1]这个范围内可以进行二分搜索,求出n的平方根。

上一篇:P3985 不开心的金明


下一篇:递归(三)从前序与中序遍历序列构造二叉树