x的平方根

题目

思路

• 类似于查找某个值，通过二分法不断缩小范围。
• 为了防止溢出，使用x / m < m来判断，而不是使用x = m * m判断。

代码

    public int mySqrt(int x) {
        if(x == 1) return 1;
        int min = 0, max = x;
        while(max - min > 1) {
            int m = (max + min) / 2;
            if(x / m < m)
                max = m;
            else
                min = m;
        }
        return min;
    }

x的平方根