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.Bkjia.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;
    }
};