69. x 的平方根

leetcode链接：
https://leetcode.cn/problems/sqrtx/

方案一

为了判断超限问题，使用了Math.pow(2, 15.5) 这里理论上是不被允许的。

int left = 0,right = x,mid = 0;

while (left <= right) {
	mid = left + (right - left) / 2;
	if (mid * mid == x) {
		return mid;
	} else if (mid * mid > x || mid > Math.pow(2, 15.5)) {
		right = mid - 1;
	} else {
		left = mid + 1;
	}
}

return (left + right) / 2;

结果

• 1017/1017 cases passed (1 ms)
• Your runtime beats 94.8 % of java submissions
• Your memory usage beats 20.62 % of java submissions (39 MB)

方案二–借鉴题解的思想

https://leetcode.cn/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/
方法二：二分查找

强制类型转换，以解决超出限制的问题

注：强制类型转换在解决整数越界问题上有较大的作用，多考虑此方法。

int left = 0,right = x,mid = 0;

while (left <= right) {
	mid = left + (right - left) / 2;
	if (mid * mid == x) {
		return mid;
	} else if ((long)mid * mid > x) {
		right = mid - 1;
	} else {
		left = mid + 1;
	}
}

return (left + right) / 2;

几乎最优方案–牛顿迭代

牛顿迭代法

https://leetcode.cn/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (Math.abs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return (int) x0;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。