Sqrt(x)

这题用二分法。
如果mid*mid == x，返回mid；

如果mid*mid < x，那么说明mid过小，应让low = mid+1，在右边继续查找

如果mid*mid > x，那么说明mid过大，应让high = mid-1，在左边继续查找

这里用了long，因为m*m可能超过integer最大值。也可以用可以用 mid < x / mid 来避免用long.

另外也可以用数学里的牛顿法。

//二分法
    public int mySqrt(int x) {
        long low = 0;
        long high = x;// or high = x/2 +1 ;这个规律可以减少一些复杂度

        while (low <= high) {
            long mid = (low + high) / 2;
            if (mid * mid <= x && x < (mid + 1) * (mid + 1)) {
                return (int) mid;
            } else if (mid * mid > x) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return 0;
    }