可以使用二分查找法或牛頓迭代法來(lái)實(shí)現(xiàn) LeetCode 問(wèn)題 69. x 的平方根。下面是使用二分查找法和牛頓迭代法的 C++ 實(shí)現(xiàn)。

二分查找法

#include <iostream>class Solution {
public:int mySqrt(int x) {if (x == 0) return 0;int left = 1, right = x, ans = 0;while (left <= right) {int mid = left + (right - left) / 2;if (mid <= x / mid) {ans = mid;left = mid + 1;} else {right = mid - 1;}}return ans;}
};int main() {Solution solution;int x = 8;std::cout << "The square root of " << x << " is " << solution.mySqrt(x) << std::endl;return 0;
}

牛頓迭代法

#include <iostream>class Solution {
public:int mySqrt(int x) {if (x == 0) return 0;double x0 = x;while (true) {double xi = 0.5 * (x0 + x / x0);if (abs(x0 - xi) < 1e-7) break;x0 = xi;}return static_cast<int>(x0);}
};int main() {Solution solution;int x = 8;std::cout << "The square root of " << x << " is " << solution.mySqrt(x) << std::endl;return 0;
}

解釋

二分查找法

1. 初始化：定義 left 為 1，right 為 x，并初始化 ans 為 0。
2. 循環(huán)：當(dāng) left 小于等于 right 時(shí)，計(jì)算 mid 作為中間值。
3. 判斷：如果 mid 的平方小于等于 x，說(shuō)明 mid 可能是平方根的一部分，更新 ans 為 mid，并移動(dòng) left 到 mid + 1。否則，移動(dòng) right 到 mid - 1。
4. 返回：循環(huán)結(jié)束后，返回 ans。

牛頓迭代法

1. 初始化：定義 x0 為 x。
2. 迭代：計(jì)算 xi，它是 x0 和 x / x0 的平均值。如果 x0 和 xi 的差異小于一個(gè)很小的值（如 1e-7），則停止迭代。
3. 更新：將 x0 更新為 xi。
4. 返回：將 x0 轉(zhuǎn)換為整數(shù)并返回。

這兩種方法都能有效地計(jì)算 x 的平方根，并且二分查找法的時(shí)間復(fù)雜度為 O(log x)，牛頓迭代法的時(shí)間復(fù)雜度為 O(log x)。你可以根據(jù)需要選擇其中一種方法。

當(dāng)然，使用圖示和例子可以更直觀地理解二分查找算法在計(jì)算平方根整數(shù)部分的過(guò)程。

例子：計(jì)算 10 的平方根的整數(shù)部分

我們以計(jì)算 10 的平方根為例，來(lái)展示整個(gè)過(guò)程。

步驟 1：初始化

• left = 1
• right = 10
• ans = 0

步驟 2：開(kāi)始二分查找

1. 第一次迭代：

   • 計(jì)算中點(diǎn) mid = left + (right - left) / 2 = 1 + (10 - 1) / 2 = 5
   • 檢查 mid * mid 和 x 的關(guān)系：5 * 5 = 25，25 > 10，因此更新 right 為 mid - 1，即 right = 4
   • 圖示：

     搜索區(qū)間: [1, 10]
     mid = 5, 5*5 > 10, 更新right = 4
     

2. 第二次迭代：

   • 計(jì)算中點(diǎn) mid = left + (right - left) / 2 = 1 + (4 - 1) / 2 = 2
   • 檢查 mid * mid 和 x 的關(guān)系：2 * 2 = 4，4 < 10，因此更新 ans 為 mid，并更新 left 為 mid + 1，即 left = 3
   • 圖示：

     搜索區(qū)間: [1, 4]
     mid = 2, 2*2 < 10, 更新left = 3, ans = 2
     

3. 第三次迭代：

   • 計(jì)算中點(diǎn) mid = left + (right - left) / 2 = 3 + (4 - 3) / 2 = 3
   • 檢查 mid * mid 和 x 的關(guān)系：3 * 3 = 9，9 < 10，因此更新 ans 為 mid，并更新 left 為 mid + 1，即 left = 4
   • 圖示：

     搜索區(qū)間: [3, 4]
     mid = 3, 3*3 < 10, 更新left = 4, ans = 3
     

4. 第四次迭代：

   • 計(jì)算中點(diǎn) mid = left + (right - left) / 2 = 4 + (4 - 4) / 2 = 4
   • 檢查 mid * mid 和 x 的關(guān)系：4 * 4 = 16，16 > 10，因此更新 right 為 mid - 1，即 right = 3
   • 圖示：

     搜索區(qū)間: [4, 4]
     mid = 4, 4*4 > 10, 更新right = 3
     

結(jié)束循環(huán)

當(dāng) left > right 時(shí)，退出循環(huán)，此時(shí) ans 保存的就是最大的滿足條件的整數(shù)。最終結(jié)果為 ans = 3，所以 10 的平方根的整數(shù)部分是 3。

代碼對(duì)應(yīng)的流程

1. 初始化 left、right 和 ans
2. 在每次迭代中計(jì)算 mid 并比較 mid * mid 和 x
   • 如果 mid * mid 小于等于 x，則更新 ans 并右移 left
   • 如果 mid * mid 大于 x，則左移 right
3. 循環(huán)結(jié)束后，返回 ans

圖示

初始區(qū)間: [1, 10]第一次迭代:
mid = 5, 5*5 > 10, 更新right = 4
搜索區(qū)間變?yōu)? [1, 4]第二次迭代:
mid = 2, 2*2 < 10, 更新left = 3, ans = 2
搜索區(qū)間變?yōu)? [3, 4]第三次迭代:
mid = 3, 3*3 < 10, 更新left = 4, ans = 3
搜索區(qū)間變?yōu)? [4, 4]第四次迭代:
mid = 4, 4*4 > 10, 更新right = 3
搜索區(qū)間變?yōu)? [4, 3]循環(huán)結(jié)束，返回 ans = 3

這樣，通過(guò)二分查找，我們成功找到并返回了 10 的平方根的整數(shù)部分 3。