Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

惭愧，看了tag才知道需要用binary search。

二分查找，需要注意把x改为long long以免数据溢出。

另外，一个正数的平方根只能在[1, x / 2 + 1)之间变动。

class Solution {
public:
    int sqrt(int x) {
        if(x < 2) return x;
        return _sqrt(x, 1, x / 2 + 1);
    }
    //[start, end)
    int _sqrt(int x, int start, int end){
        if(end - start == 1){
            return start * start <= x? start: start - 1;
        }
        long long mid = (start + end) / 2;
        if(mid * mid > x){
            return _sqrt(x, start, mid);
        }
        else{
            return _sqrt(x, mid, end);
        }
    }
};

牛顿法

对于n找一个x使x^2 = n

记f(x) = x^2 – n，即求x使f(x) = 0

牛顿法找零点。

给定f(x)曲线上任意一点(x0，f(x0))作曲线在该点的切线。切线方程为：

(y-f(x0)) / (x – x0) = f'(x0)

f'(x0)=2×0

化简并令y=0，求x得

x=x0/2 + n / (2×0)

x即为x0的切线与x轴的交点。

再求(x,f(x))的切线与x轴的交点，不断迭代。

当两个相邻的x值相等时，认为结束。

下面的代码并没有AC。很奇怪，卡在了1上。

class Solution {
public:
    int sqrt(int x) {
        if(x == 0) return 0;
        double x0 = 0;
        double x1 = 1;
        while(x0 != x1){
            x0 = x1;
            x1 = x1 / 2 + x / 2 / x1;
        }
        return (int)x1;
    }
};