leetcode 69. x 的平方根

可以使用二分查找法或牛顿迭代法来实现 LeetCode 问题 69. x 的平方根。下面是使用二分查找法和牛顿迭代法的 C++ 实现。

二分查找法

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

牛顿迭代法

#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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

解释

二分查找法

1. 初始化：定义 left 为 1，right 为 x，并初始化 ans 为 0。
2. 循环：当 left 小于等于 right 时，计算 mid 作为中间值。
3. 判断：如果 mid 的平方小于等于 x，说明 mid 可能是平方根的一部分，更新 ans 为 mid，并移动 left 到 mid + 1。否则，移动 right 到 mid - 1。
4. 返回：循环结束后，返回 ans。

牛顿迭代法

1. 初始化：定义 x0 为 x。
2. 迭代：计算 xi，它是 x0 和 x / x0 的平均值。如果 x0 和 xi 的差异小于一个很小的值（如 1e-7），则停止迭代。
3. 更新：将 x0 更新为 xi。
4. 返回：将 x0 转换为整数并返回。

这两种方法都能有效地计算 x 的平方根，并且二分查找法的时间复杂度为 O(log x)，牛顿迭代法的时间复杂度为 O(log x)。你可以根据需要选择其中一种方法。

当然，使用图示和例子可以更直观地理解二分查找算法在计算平方根整数部分的过程。

例子：计算 10 的平方根的整数部分

我们以计算 10 的平方根为例，来展示整个过程。

步骤 1：初始化

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

步骤 2：开始二分查找

1. 第一次迭代：

   • 计算中点 mid = left + (right - left) / 2 = 1 + (10 - 1) / 2 = 5
   • 检查 mid * mid 和 x 的关系：5 * 5 = 25，25 > 10，因此更新 right 为 mid - 1，即 right = 4
   • 图示：

     搜索区间: [1, 10]
     mid = 5, 5*5 > 10, 更新right = 4
     1
     2

2. 第二次迭代：

   • 计算中点 mid = left + (right - left) / 2 = 1 + (4 - 1) / 2 = 2
   • 检查 mid * mid 和 x 的关系：2 * 2 = 4，4 < 10，因此更新 ans 为 mid，并更新 left 为 mid + 1，即 left = 3
   • 图示：

     搜索区间: [1, 4]
     mid = 2, 2*2 < 10, 更新left = 3, ans = 2
     1
     2

3. 第三次迭代：

   • 计算中点 mid = left + (right - left) / 2 = 3 + (4 - 3) / 2 = 3
   • 检查 mid * mid 和 x 的关系：3 * 3 = 9，9 < 10，因此更新 ans 为 mid，并更新 left 为 mid + 1，即 left = 4
   • 图示：

     搜索区间: [3, 4]
     mid = 3, 3*3 < 10, 更新left = 4, ans = 3
     1
     2

4. 第四次迭代：

   • 计算中点 mid = left + (right - left) / 2 = 4 + (4 - 4) / 2 = 4
   • 检查 mid * mid 和 x 的关系：4 * 4 = 16，16 > 10，因此更新 right 为 mid - 1，即 right = 3
   • 图示：

     搜索区间: [4, 4]
     mid = 4, 4*4 > 10, 更新right = 3
     1
     2

结束循环

当 left > right 时，退出循环，此时 ans 保存的就是最大的满足条件的整数。最终结果为 ans = 3，所以 10 的平方根的整数部分是 3。

代码对应的流程

1. 初始化 left、right 和 ans
2. 在每次迭代中计算 mid 并比较 mid * mid 和 x
   • 如果 mid * mid 小于等于 x，则更新 ans 并右移 left
   • 如果 mid * mid 大于 x，则左移 right
3. 循环结束后，返回 ans

图示

初始区间: [1, 10]

第一次迭代:
mid = 5, 5*5 > 10, 更新right = 4
搜索区间变为: [1, 4]

第二次迭代:
mid = 2, 2*2 < 10, 更新left = 3, ans = 2
搜索区间变为: [3, 4]

第三次迭代:
mid = 3, 3*3 < 10, 更新left = 4, ans = 3
搜索区间变为: [4, 4]

第四次迭代:
mid = 4, 4*4 > 10, 更新right = 3
搜索区间变为: [4, 3]

循环结束，返回 ans = 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这样，通过二分查找，我们成功找到并返回了 10 的平方根的整数部分 3。