本期精選題解由我們的用戶“liweiwei1419”傾情撰寫，一起來看看吧！

69. X 的平方根（點擊查看題目）

題目描述

實現 int sqrt(int x) 函數。

計算並返回 x 的平方根，其中 x 是非負整數。

由於返回類型是整數，結果只保留整數的部分，小數部分將被捨去。

示例 1:

示例 2:

解決方案

二分查找法應用於搜索平方根的思想很簡單，其實就是“猜”，但是是有策略的“猜”，用“排除法”在有限的區間裡，一次排除一半的區間元素，最後只剩下一個數，這個數就是題目要求的向下取整的平方根整數。

牛頓法最初提出的時候，是用於求解方程的根，它的基本思想是“以直代曲”，在迭代中搜索得到方程的近似解。

方法一：二分法

思路分析：使用二分法搜索平方根的思想很簡單，就類似於小時候我們看的電視節目中的“猜價格”遊戲，高了就往低了猜，低了就往高了猜，範圍越來越小。因此，使用二分法猜算術平方根就很自然。

一個數的平方根肯定不會超過它自己，不過直覺還告訴我們，一個數的平方根最多不會超過它的一半，例如 8 的平方根，8 的一半是 4，4^2 = 16 > 8，如果這個數越大越是如此，因此我們要計算一下，這個邊界是多少。為此，解如下不等式：

意即：如果一個數的一半的平方大於它自己，那麼這個數的取值範圍。解以上不等式得 a ≥ 4 或者 a ≤ 0。

於是邊界值就是 4，那麼對0、1、2、3 分別計算結果，很容易知道，這 4 個數的平方根依次是 0、1、1、1 。

注意：這 4 個特值如果沒有考慮到，有可能導致你設置的搜索邊界不正確。在使用二分法尋找平方根的時候，要特別注意邊界值的選擇，以下給出兩個參考代碼。

參考代碼 1：所有的數都放在一起考慮，為了照顧到 0 把左邊界設置為 0，為了照顧到 1 把右邊界設置為 x // 2 + 1 。

Python 實現

Java 實現

Java 代碼要注意到：如果中點 mid 聲明為 int 類型，針對大整型測試用例通不過，因此變量需要聲明為 long 類型，下同。

參考代碼 2

：事實上，只要單獨照顧一下 0 這個特例就可以了。

​Python 實現

Java 實現

注意： 這裡二分法的使用是有技巧的（如果你沒有意識到，這裡很可能是個“坑”），下面我就上面註釋中提到的：

注意：這裡一定取右中位數，如果取左中位數，代碼可能會進入死循環。

做一些解釋。當 x = 9 的時候，我們不妨給“錯誤的”代碼加上一些調試語句，這樣你就會更清晰地發現死循環在什麼時候出現，例如：

Python 實現

控制檯輸出

分析：如果取中點為左中位數，你看到死循環發生在 left = 3， right = 4 的時候，此時 區間只有 2 個元素。這是為什麼呢？

此時索引區間 [3, 4] 的中位數為左中位數，即 mid = 3 ，此時 square = 9 < 9 不成立，進入 left = mid 這個分支，你發現問題了嗎，區間不發生收縮，即下一輪循環的索引區間還是 [3, 4]，此時中位數還取左中位數，即mid = 3 ，square = 9 < 9 不成立，又進入 left = mid 這個分支，死循環就是這樣產生的。

接著，請你把 mid = left + (right - left) // 2 改成mid = left + (right - left + 1) // 2 ，即選擇右中位數，再觀察一下控制檯輸出，就知道此時為什麼要選右中位數了。

這個二分法模板我用了很久，感覺非常好用。於是我專門把這個二分法模板好用的地方、使用它的技巧和注意事項整理在了「力扣 」第 35 題：搜索插入位置的題解 《特別好用的二分查找法模板（Python 代碼、Java 代碼）》，希望能對大家有所幫助。

複雜度分析：

時間複雜度：O(log N)，二分法的時間複雜度是對數級別的。

空間複雜度：O(1)，使用了常數個數的輔助空間用於存儲和比較。

總結： 使用二分查找法搜索，注意特值對搜索邊界的影響。

以下這部分內容是根據與用戶 @lukas 在本題解下的討論而添加的。

在這裡補充一下，如果你實在不太想分析 a 的平方根可能的上界，之前說了，它肯定不會超過 a 自己，即使你把上界寫成一個很大的數，例如 999999，這個數必須得是力扣的測試用例都達不到的數，在二分查找的過程中，不符合要求的數每次會被很快砍掉一半。

參考代碼 3：乾脆我不討論 a 的邊界，讓二分法去排除不符合的區間吧，對數級別的時間複雜度對性能不會有很大影響。

Python 實現

Java 實現

方法二：牛頓法

使用牛頓法可以得到一個正實數的算術平方根，因為題目中說“結果只保留整數部分”，因此，我們把使用牛頓法得到的浮點數轉換為整數即可。

這裡給出牛頓法的思想：

在迭代過程中，以 直線代替曲線，用一階泰勒展式（即在當前點的切線）代替原曲線，求直線與 X 軸的交點，重複這個過程直到收斂。

說明：

1、以上圖片來自《牛頓法與擬牛頓法》；

2、@LOAFER 的題解《牛頓迭代法》 的圖和文字說明更好，而知乎問答《如何通俗易懂地講解牛頓迭代法求開方？數值分析？》裡面乾貨就更多了，建議大家出門左轉觀看，我這篇題解只是展示一下迭代公式如何計算。

注意：牛頓法得到的是平方根的浮點型精確值（可能會有一定誤差），根據題目中的要求，把最後得到的這個數轉換為 int 型，即去掉小數部分即可。

對“牛頓法”感興趣的朋友們可以查一下牛頓法的應用：一個是求方程的根，另一個是求解最優化問題，在這裡就不展開了。

參考代碼 4：

Python 實現

Java 實現

說明：1e-6 是科學計數法，表示 1 乘以 10 的負 6 次方，也就是 0.000001。有的地方使用 epsilon 表示 1e-6 ，用來抵消浮點運算中因為誤差造成的相等無法判斷的情況，它通常是一個非常小的數字，具體多小要根據你的精度需求來設置。

​複雜度分析：

時間複雜度：（待討論）

空間複雜度：O(1)，使用了常數個數的輔助空間用於存儲和比較。