【LeetCode】69. Sqrt(x) (2 solutions)

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

解法一：牛顿迭代法

求n的平方根，即求f(x)=x²-n的零点

设初始值为x₀，注，不要设为0，以免出现除数为0，见后。

则过(x₀,f(x₀))点的切线为g(x)=f(x₀)+f'(x₀)*(x-x₀)

g(x)与x轴的交点为x₁=x₀-f(x₀)/f'(x₀)

递推关系为x_n+1=x_n-f(x_n)/f'(x_n)

当收敛时即为解。

class Solution {
public:
    int sqrt(int x) {
        double x0 = 1;
        double x_next = -(x0*x0 - x)/(2*x0) + x0;
        while(fabs(x0-x_next) > 0.00001)
        {
            x0 = x_next;
            x_next = -(x0*x0 - x)/(2*x0) + x0;
        }
        return x0;
    }
};

解法二：二分法

注意返回为int，结果会取整。

class Solution {
public:
    int sqrt(int x) {
        long long low = 0;
        long long high = x;
        long long mid;
        while(low <= high)
        {
            mid = (low+high)/2;
            long long result = mid*mid;
            if(result == x)
                return mid;
            else if(result > x)
                high = mid-1;
            else
                low = mid+1;
        }
        return high;
    }
};