LeetCode 69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

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 we want to return an integer, the decimal part will be truncated.

解析：
采用二分法，对于一个非负数，其平方根不会大于（n/2+1），在[0, n/2+1]这个范围内可以进行二分搜索，求出n的平方根。
需要考虑边界情况，如超过最大值的情况。

class Solution {
public:
    int mySqrt(int x) {
        long long begin = 0;
        long long end = x/2+1;
        while(begin <= end)
        {
            long long mid = (begin + end) /2;
            long long square = mid * mid;
            if(square == x)
            {
               return mid; 
            }else if(square < x)
            {
                begin = mid + 1;
            }else{
                end = mid -1;
            }                
        }
        return end;
    }
};

方法2 牛顿法:

牛顿法法主要是为了解决非线性优化问题，其收敛速度比梯度下降速度更快。 把\(f(x)\)在点\(x_{0}\)的某邻域内展开成泰勒级数如下表示：
取其线性部分（即泰勒展开的前两项），并令其等于0，即

以此作为非线性方程\(f(x)=0\)的近似方程，若\(f^{‘}(x)!=0\)，则其解为

这样，得到牛顿迭代法的一个迭代关系式：

在此令\(f(x)=x^2-n\)，则迭代公式为：
\(x_{n+1}=x_{n}-\frac{f(x_{n})}{f^\prime(x_{n})}=x_{n}-\frac{x_{n}^2-n}{2x_{n}}\)
判断\(x_{n}\)是否是f(x)=0的解有两种方法：
一是直接计算\(f(x_{n})\)的值判断是否为0，二是判断前后两个解\(x_{n},x_{n-1}\)是否无限接近。

class Solution {
public:
    int mySqrt(int x) {
        if(x==0)
            return x;
        double last = 0;
        double result = 1;
        double delta  = 0.0001;
        while (abs(result-last) >= delta)
        {
          last = result;
          result = (result + x / result) / 2;
        }
        return int(result);
    }
};

参考：
https://segmentfault.com/a/1190000003697204
http://www.cnblogs.com/AnnieKim/archive/2013/04/18/3028607.html