题目

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,

由于返回类型是整数，小数部分将被舍去。

题解

方法一：二分查找

找到中间的数: mid = start + (end - start) / 2 而且: mid * mid <= x && (mid + 1) * (mid + 1) > x 但是这么写超出了 Integer 的范围了:

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        int start = 1, end = x;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (mid * mid <= x  && (mid + 1) * (mid + 1) > x)// Found the result
                return mid;
            else if (mid > x / mid)// Keep checking the left part
                end = mid;
            else
                start = mid + 1;// Keep checking the right part
        }
        return start;
    }
}

所以改变一下: mid * mid <= x && (mid+1)(mid+1) > x 下面的 code 为 AC 版本:

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        int start = 1, end = x;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (mid <= x / mid && (mid + 1) > x / (mid + 1))// Found the result
                return mid;
            else if (mid > x / mid)// Keep checking the left part
                end = mid;
            else
                start = mid + 1;// Keep checking the right part
        }
        return start;
    }
}

python 版本

class Solution:
    def mySqrt(self, x):
        start, end = 0, x
        while start <= end:
            # 结果都计算为整数
            mid = start + (end - start) // 2
            if mid * mid <= x < (mid + 1) * (mid + 1):
                return mid
            elif x < mid * mid:
                end = mid
            else:
                start = mid + 1

牛顿迭代法

基本思想：把非线性方程线性化，用线性方程的解逐步逼近原方程的解

求某个数(比如 8)的平方根其实就是求解 f(x) = x^2 - 8 = 0 的解

如上图

点(x[k+1], 0)满足该方程 0 = f （ x[k]） + f'(x[k])(x[k+1] - x[k]) 得到牛顿迭代法的迭代公式:

x[k+1] = x[k] - f(x[k]) / f'(x[k])

回到求 8 的平方根

x[k+1] = x[k] - (x[k] - 8) / (2 * x[k]) = (x[k] + 8 / x[k]) / 2

就这样一直逼近到 x[k] * x[k] <= 8

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        long i = x;
        while(i > x / i)
            i = (i + x / i) / 2;
        return (int)i;
    }
}

python 版本

class Solution:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 0:
            return 0
        i = x
        while int(i) > int(x / i):
            i = (i + x / i) / 2
        return int(i)