LeetCode 69. Sqrt(x)

题目信息：

Implement int sqrt(int x).

Compute and return the square root of x. where x is guaranteed to be a non-negative integer.

Example 1:

Input: 4 Output: 2

Example 2:

Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

解法一：二分法$O(logx)$ $O(1)$.

分析：$\forall y \in [a,b]$,存在 $y_{max}$,满足$y_{max}^2 \leq x$.二分区间求出$y_{max}$.

$a,b$分别为区间上下界

代码：

class Solution {
public:
    int mySqrt(int x) {
        //the ans is not greater than x/2+1.
        int l = 0, r = x/2+1;
        while(l<r) {
            //to avoid the overflow
            int mid = (l+1ll+r)/2;
            if(mid<=x/mid) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};

解法二：牛顿迭代法

分析：利用数值分析中学习的求解方程的根来解出$x^2=a$的根

$x_{n+1}=x_n- \frac{f(x_n)}{f’(x_n)}$, $f(x) = x^2-a, f’(x) = 2x$具体推导过程见链接。可化简为$x_{n+1} = x_n - \frac{x_n^2-a}{2x_n} = \frac{x_n+\frac{a}{x_n}}{2}$

代码：

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

链接：

Newton’s method

马同学-牛顿迭代法

牛顿法复杂度分析