題目
Implement int sqrt(int x).
Compute and return the square root of x.
解題思路
題目讓我們實現(xiàn) sqrt 函數(shù)沾谓，具體實現(xiàn)有以下兩種方法：
1. 二分查找
第一個方法是二分查找践盼，范圍為 [1, Integer.MAX_VALUE]章贞，看哪個數(shù)的平方會等于 x绞佩，這里需要注意的是 不能直接判斷 midmid == x，因為 midmid 數(shù)值可能很大，從而導致溢出「炫纾可以轉(zhuǎn)化為判斷 mid == x/mid。該算法的時間復雜度為 O(log(Integer.MAX_VALUE))夭织。
2. Newton's method
牛頓大法好厌蔽，沒想到求一個數(shù)的平方根也可以用到牛頓方法。下面是我在網(wǎng)上找到的有關(guān) Newton's method 的介紹：
牛頓迭代法（Newton's method）又稱為牛頓-拉夫遜方法（Newton-Raphson method）摔癣，它是牛頓在17世紀提出的一種在實數(shù)域和復數(shù)域上近似求解方程的方法奴饮。多數(shù)方程不存在求根公式，因此求精確根非常困難择浊，甚至不可能戴卜，從而尋找方程的近似根就顯得特別重要。方法使用函數(shù)f(x)的泰勒級數(shù)的前面幾項來尋找方程f(x) = 0的根琢岩。牛頓迭代法是求方程根的重要方法之一投剥，其最大優(yōu)點是在方程f(x) = 0的單根附近具有平方收斂，而且該法還可以用來求方程的重根担孔、復根江锨。另外該方法廣泛用于計算機編程中。
設(shè)r是f(x) = 0的根糕篇，選取x0作為r初始近似值啄育，過點（x0,f(x0)）做曲線y = f(x)的切線L，L的方程為y = f(x0)+f'(x0)(x-x0)拌消，求出L與x軸交點的橫坐標 x1 = x0-f(x0)/f'(x0)挑豌，稱x1為r的一次近似值。
過點（x1,f(x1)）做曲線y = f(x)的切線，并求該切線與x軸交點的橫坐標 x2 = x1-f(x1)/f'(x1)氓英，稱x2為r的二次近似值侯勉。重復以上過程，得r的近似值序列铝阐，其中x(n+1)=x(n)－f(x(n))/f'(x(n))址貌，稱為r的n+1次近似值，上式稱為牛頓迭代公式徘键。
根據(jù)牛頓迭代的原理练对，將 f(x) = x^2 代進去即可得到以下的迭代公式：X(n+1)=[X(n)+p/X(n)]/2，具體代碼見參考代碼啊鸭。
參考代碼
1. 二分查找
class Solution {
public:
int mySqrt(int x) {
if (x == 0)
return 0;
int left = 1, right = INT_MAX;
while (true) {
int mid = left + (right - left)/2;
if (mid > x/mid) {
right = mid - 1;
}
else {
if (mid + 1 > x/(mid + 1))
return mid;
left = mid + 1;
}
}
}
};
2. Newton's method
class Solution {
public:
int mySqrt(int x) {
long r = x;
while (r*r > x)
r = (r + x/r) / 2;
return r;
}
};
