題目

實(shí)現(xiàn) int sqrt(int x) 函數(shù)。
計(jì)算并返回 x 的平方根，其中 x 是非負(fù)整數(shù)。
由于返回類型是整數(shù)，結(jié)果只保留整數(shù)的部分，小數(shù)部分將被舍去。
示例 1:

輸入: 4
輸出: 2

示例 2:

輸入: 8
輸出: 2

說(shuō)明:
8 的平方根是 2.82842...，由于返回類型是整數(shù)，小數(shù)部分將被舍去。

思路

我這邊了解到的方法有二分搜索和牛頓迭代法

• 二分搜索思路比較簡(jiǎn)單，其實(shí)就是試數(shù)的一個(gè)過(guò)程，不過(guò)其中有一個(gè)小tips，x的平方根不會(huì)大于x / 2 + 1，這樣，可以縮小范圍，減少一些計(jì)算

• 牛頓迭代法需要一些數(shù)學(xué)理論如下：

為了方便理解，就先以本題為例。計(jì)算x² = n的解，令f(x)=x²-n，相當(dāng)于求解f(x)=0的解，如圖所示。

首先取x₀，如果x₀不是解，做一個(gè)經(jīng)過(guò)(x₀,f(x₀))這個(gè)點(diǎn)的切線，與x軸的交點(diǎn)為x₁。同樣的道理，如果x₁不是解，做一個(gè)經(jīng)過(guò)(x₁,f(x₁))這個(gè)點(diǎn)的切線，與x軸的交點(diǎn)為x₂。以此類推。
以這樣的方式得到的x_i會(huì)無(wú)限趨近于f(x)=0的解。
判斷x_i是否是f(x)=0的解有兩種方法：
（1）一是直接計(jì)算f(x_i)的值判斷是否為0
（2）二是判斷前后兩個(gè)解x_i和x_i-1是否無(wú)限接近。經(jīng)過(guò)(x_i, f(x_i))這個(gè)點(diǎn)的切線方程為f(x) = f(x_i) + f’(x_i)(x - x_i)，其中f'(x)為f(x)的導(dǎo)數(shù)，本題中為2x。令切線方程等于0，即可求出x_i+1=x_i - f(x_i) / f'(x_i)。繼續(xù)化簡(jiǎn)，x_i+1=x_i - (x_i² - n) / (2x_i) = x_i - x_i / 2 + n / (2x_i) = x_i / 2 + n / 2x_i = (x_i + n/x_i) / 2。
有了迭代公式，程序就好寫(xiě)了。關(guān)于牛頓迭代法，可以參考wikipedia以及百度百科。

代碼

//二分搜索法
//最開(kāi)始用的是PHP，結(jié)果超時(shí)，emmm，然后上C語(yǔ)言了
int mySqrt(int x) {
    long long i = 0;
    long long j = x / 2 + 1;
    while (i <= j)
    {
        long long mid = (i + j) / 2;
        long long sq = mid * mid;
        if (sq == x) return mid;
        else if (sq < x) i = mid + 1;
        else j = mid - 1;
    }
    return j;
}

//牛頓迭代法
double sqrt(double x) {
    if (x == 0) return 0;
    double last = 0.0;
    double res = 1.0;
    while (res != last)
    {
        last = res;
        res = (res + x / res) / 2;
    }
    //return res; 用此行則返回double，但是此題要求返回整數(shù)
    return int(res);
}

歡迎大家關(guān)注我的公眾號(hào)

半畝房頂