LeetCode----Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

思路： 其实就是求解 非线性方程 x^2 = A. (A为开方的数)

一般形式是 求解 f (x) = 0

解法1： 牛顿切线法

这是牛顿在 1736年提出的方法，其实思想非常简单， 如下图。

给定一个初始值 x0, 在点 （x0, f(x0)）处画一切线，求切线与 x轴的交点得到 x1, 依次类推。。

得到以下的迭代式

< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHByZSBjbGFzcz0="brush:java;">class Solution { public: int sqrt(int x) { if(x < 2) return x; double root(x); while(fabs(root*root - x) >= 1) /*直到误差足够小*/ { root = (root*root + x)/(2*root); } return root; } };

解法2： 二分法

class Solution {
public:
    int sqrt(int x) {
      if(x == 1) return 1;
      int left(0), right(x);
      int mid(0);
      
      while(left+1 < right){
          mid = left + (right-left)/2;
          if(mid > x/mid){ //mid*mid-x 溢出
              right = mid;
          }
          else if(mid < x/mid){
              left = mid;
          }
          else{
              return mid;
          }
      }
      return left;
    }
};