题目

Implement int sqrt(int x).

Compute and return the square root of x.

频度： 4

解题之法

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

分析

这种解法主要利用了牛顿迭代法。

226.jpg

这种算法的原理很简单，我们仅仅是不断用(x,f(x))的切线来逼近方程x^{2-a=0的根。根号a实际上就是x}2-a=0的一个正实根，这个函数的导数是2x。

具体推导如下：

227.jpg

代入f(x)=x^{2-a得到x-(x}2-a)/(2x)，也就是(x+a/x)/2。