最近忙里偷閑，每天刷一道 LeetCode 的簡(jiǎn)單題保持手感烫映，發(fā)現(xiàn)簡(jiǎn)單題雖然很容易 AC沼本，但若去了解其所有的解法，也可學(xué)習(xí)到不少新的知識(shí)點(diǎn)锭沟，擴(kuò)展知識(shí)的廣度抽兆。
創(chuàng)作本文的思路來(lái)源于：LeetCode Problem 69. x 的平方根
簡(jiǎn)述題目大意（不想跳轉(zhuǎn)鏈接，可以看這里）：給定一個(gè)非負(fù)整數(shù) x族淮，要求計(jì)算并返回 x 的平方根（取整）辫红。例如，輸入 4瞧筛，則輸出 2厉熟；輸入 8，則輸出 2（8 的平方根是 2.82842……较幌，由于返回類型是整數(shù)揍瑟，因此小數(shù)部分被舍去）。即給定一個(gè) 乍炉，我們要計(jì)算出
绢片。
最簡(jiǎn)單最直覺(jué)的方法自然是從 0 開(kāi)始遍歷滤馍，直到找到第一個(gè)其平方值大于 的數(shù)
，則
即是答案底循。對(duì)于任意的
巢株，其取整后平方根一定在
區(qū)間上，代碼如下：
int sqrt(int x)
{
if (x == 0)
return x;
int ans = 1;
while (ans <= x / ans)
ans++;
return ans - 1;
}
這里需要注意的有兩點(diǎn)：
- 第 6 行代碼中熙涤，
while的判斷條件可以避免溢出阁苞。很大概率上，你可能會(huì)寫成while (ans * ans <= x)祠挫，這更自然那槽、更直觀，但當(dāng)ans的值很大時(shí)等舔，ans * ans的結(jié)果可能會(huì)超過(guò)int類型的最大表示范圍骚灸。舉個(gè)例子，比如我們要計(jì)算的取整平方根（其值為
慌植，即
）甚牲，算法會(huì)將
ans遍歷到第一個(gè)平方超過(guò)后停止蝶柿。如果
int類型能夠表示的最大值丈钙，那么當(dāng)ans遍歷到ans * ans的結(jié)果就超出了int類型的表示范圍只锭。 - 由于在
while的循環(huán)判斷中著恩，我們用除法代替了乘法院尔，因此ans便不能再?gòu)?0 開(kāi)始遍歷（否則會(huì)導(dǎo)致除零錯(cuò)誤）蜻展。為此，我們可以在算法開(kāi)始單獨(dú)處理的情況邀摆，然后讓
ans從 1 開(kāi)始遍歷纵顾。
作為一道簡(jiǎn)單題，這種暴力樸素的算法自然是可以 AC 的栋盹。但其效率極低（需要遍歷 次）施逾，在 LeetCode 上的時(shí)間效率只能快過(guò)約 5% 的用戶，使用 C++ 語(yǔ)言的運(yùn)行時(shí)間平均要 90ms 以上例获。因此汉额，本文提供了兩種更加高效的算法：二分查找法和牛頓法。
1. 二分查找法
如果你在暴力求解的基礎(chǔ)上繼續(xù)思考榨汤，很大概率會(huì)想到用二分搜索求解蠕搜。
沒(méi)錯(cuò)，思考暴力求解的策略收壕，我們?cè)趨^(qū)間 上搜索解妓灌，而搜索區(qū)間
天然是有序的轨蛤，自然可以用二分搜索代替線性搜索，以大大提高搜索效率虫埂。
更進(jìn)一步的祥山，我們還可以縮小我們的搜索區(qū)間。直覺(jué)告訴我們掉伏，對(duì)于一個(gè)非負(fù)整數(shù) 缝呕，其
應(yīng)該不會(huì)大于
（例如，
斧散，小于
）岳颇。我們可以證明：
通過(guò)證明我們可以得知颅湘，當(dāng)所求的 大于等于
時(shí)话侧，
sqrt(x) 的搜索空間為 ，對(duì)于
的情況闯参，我們只要特殊處理即可（這里我們也可以得到結(jié)論：當(dāng)
時(shí)瞻鹏，
，然后單獨(dú)處理
的情況）鹿寨。代碼：
int sqrt(int x)
{
if (x < 2) // 處理特殊情況
return x;
int left = 1, right = x / 2;
while (left <= right) {
# 避免溢出新博，相當(dāng)于 mid = (left + right) / 2
int mid = left + ((right - left) >> 1);
if (mid == x / mid)
return mid;
else if (mid > x / mid)
right = mid - 1;
else
left = mid + 1;
}
return right;
}
在這里解釋一下最后的返回值為什么是 right。對(duì)于二分查找脚草，其搜索空間會(huì)不斷收縮到 left == right（關(guān)于二分查找赫悄，這里不多贅述，自行手動(dòng)模擬即可）馏慨，此時(shí) mid埂淮、left和 right 三者的值相等（mid = (left + right) / 2）。根據(jù)二分查找的搜索范圍的收縮條件可知写隶，left（或 mid）左側(cè)的值都小于等于 倔撞，
right（或 mid）右側(cè)的值都大于 ，此時(shí)（
while 的最后一次循環(huán)）慕趴，判斷 mid 的平方與 x 的大小痪蝇，有三種情況：
-
mid == x / mid。則在循環(huán)內(nèi)直接返回mid的值冕房。 -
mid > x / mid躏啰。這種情況下，因?yàn)?mid左側(cè)的值都小于等于耙册，而
mid的值大于mid-1即是答案。而按照分支條件觅玻，執(zhí)行right = mid - 1想际，可知right的值正是應(yīng)返回的值培漏。此時(shí)，循環(huán)結(jié)束胡本，應(yīng)返回right牌柄。 -
mid <= x / mid。這種情況下侧甫，mid珊佣、left和right正是計(jì)算答案（右邊的值都大于left = mid + 1咒锻，循環(huán)結(jié)束。此時(shí)守屉，mid和right的值為計(jì)算結(jié)果惑艇。
綜合上面三點(diǎn)可知，如果 while 循環(huán)結(jié)束拇泛，則 right 保存的值一定是計(jì)算結(jié)果滨巴。
和之前的暴力法相比，使用二分查找的思想求解 sqrt(x)俺叭，只需要循環(huán)遍歷 次恭取；空間復(fù)雜度為
。
2. 牛頓—拉弗森迭代法
牛頓—拉弗森迭代法（簡(jiǎn)稱牛頓法）使用以直代曲的思想熄守，是一種求解函數(shù)的方法蜈垮，不僅僅適用于求解開(kāi)方計(jì)算。當(dāng)然使用牛頓法求解函數(shù)也存在很多坑裕照，但對(duì)于求解開(kāi)方而言攒发，牛頓法是安全的。關(guān)于這一方法牍氛，你需要掌握一定的高等數(shù)學(xué)知識(shí)晨继，想了解詳細(xì)的內(nèi)容烟阐，可以參考鏈接：如何通俗易懂地講解牛頓迭代法求開(kāi)方搬俊？數(shù)值分析？—馬同學(xué)的回答
簡(jiǎn)單的理解蜒茄，可以參考圖片：
圖片來(lái)源：牛頓法與擬牛頓法
給定任意一個(gè)非負(fù)整數(shù) 唉擂，我們想要找到一個(gè)
，這相當(dāng)于我們要計(jì)算函數(shù)
的根檀葛。我們首先需要先給出一個(gè)猜測(cè)值
玩祟，不妨令
（證明見(jiàn)第一小節(jié)），然后在
處作函數(shù)的切線屿聋，切線與
軸的交點(diǎn)空扎，即為一次迭代后的值
藏鹊。若
不是要得到的結(jié)果，則繼續(xù)迭代转锈，在
處作函數(shù)的切線盘寡，切線與
軸的交點(diǎn)，即為第二次迭代后的值
撮慨。以此類推竿痰，直到得到
。
現(xiàn)在我們來(lái)推導(dǎo)迭代式砌溺。對(duì)于 影涉，其函數(shù)值為
，則對(duì)于點(diǎn)
规伐，可得其切線方程：
又因?yàn)? 為切線與
軸的交點(diǎn)蟹倾，所以令
，可得：
現(xiàn)在猖闪，我們就可以根據(jù)迭代式編寫代碼了：
int sqrt(int x)
{
// 避免除零錯(cuò)誤喊式，單獨(dú)處理 x = 0 的情況
if (x == 0)
return x;
int t = x / 2 + 1;
while (t > x / t)
t = (t + x / t) / 2;
return t;
}
為了確保算法是正確的，我們還需要一些額外的證明萧朝。首先岔留，證明迭代式是單調(diào)遞減的：
可知，在區(qū)間 上检柬，
献联。
然后，我們還要證明迭代式是可以收斂到 的：
因此何址，當(dāng) while 循環(huán)結(jié)束時(shí)里逆，我們可以得到正確的答案。
關(guān)于牛頓法求 sqrt(x) 的時(shí)間復(fù)雜度用爪，筆者目前也沒(méi)有搞清楚原押，有了解的童鞋歡迎交流~。不過(guò)通過(guò)查詢資料偎血，以及實(shí)際測(cè)試诸衔，可知牛頓法的時(shí)間效率優(yōu)于二分搜索法。
