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;
    }

牛顿迭代

迭代公式： 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的平方根。