69. Sqrt(x) (Easy)

Implement int sqrt(int x).

Compute and return the square root of x.

Solution 1: Binary Search

这道题要求我们求平方根，我们能想到的方法就是算一个候选值的平方，然后和x比较大小，为了缩短查找时间，我们采用二分搜索法来找平方根，由于求平方的结果会很大，可能会超过int的取值范围，所以我们都用long long来定义变量，这样就不会越界，代码如下：

version 1: 9ms

class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x/2+1;
        while (l <= r) {
            long mid = (l+r)/2;
            long sq = mid*mid;
            if (sq == x) return mid;
            else if (sq < x) l = mid+1;
            else r = mid-1;
        }
        return r;

    }
};

version 2: 3ms

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;
        int l = 1, r = x/2+1;
        while (true) {
            int mid = l+(r-l)/2;
            if (mid > x/mid) r = mid-1;
            else {
                // mid^2 <= x < (mid+1)^2
                if (mid+1 > x/(mid+1)) return mid;
                else l = mid+1;
            }
        }
        return 0;
    }
};

Solution 2: Math

这道题还有另一种解法，是利用牛顿迭代法，记得高数中好像讲到过这个方法，是用逼近法求方程根的神器，在这里也可以借用一下，可参见网友Annie Kim's Blog的博客，因为要求$$x^2 = n$$的解，令$$f(x)=x^2-n$$，相当于求解$$f(x)=0$$的解，可以求出递推式如下：

$$f(x{i+1}) = f(x_i) + f'(x_i)(x{i+1}-x_i) = 0$$ and $$f'(x) = 2x$$

$$x_{i+1}=x_i - ({x_i}^2 - n) / (2x_i) = x_i - x_i / 2 + n / (2x_i) = x_i / 2 + n / 2x_i = (x_i + n/x_i) / 2$$

version 1: 6ms

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;
        double res = 1, last = 0;
        while (res != last) {
            last = res;
            res = (res+x/res)/2;
        }
        return res;
    }
};

version 2: 6ms

class Solution {
public:
    int mySqrt(int x) {
        long res = x;
        while (res*res > x) {
            res = (res+x/res)/2;
        }
        return res;
    }
};