福建省建设信息网站,wordpress 404跳转,玉环县企业网站建设,工程建设最好的网站可以使用二分查找法或牛顿迭代法来实现 LeetCode 问题 69. x 的平方根。下面是使用二分查找法和牛顿迭代法的 C 实现。
二分查找法
#include iostreamclass Solution {
public:int mySqrt(int x) {if (x 0) return 0;int left 1, right x, ans 0;while (left 实现。
二分查找法
#include iostreamclass 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 iostreamclass 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_castint(x0);}
};int main() {Solution solution;int x 8;std::cout The square root of x is solution.mySqrt(x) std::endl;return 0;
}解释
二分查找法
初始化定义 left 为 1right 为 x并初始化 ans 为 0。循环当 left 小于等于 right 时计算 mid 作为中间值。判断如果 mid 的平方小于等于 x说明 mid 可能是平方根的一部分更新 ans 为 mid并移动 left 到 mid 1。否则移动 right 到 mid - 1。返回循环结束后返回 ans。
牛顿迭代法
初始化定义 x0 为 x。迭代计算 xi它是 x0 和 x / x0 的平均值。如果 x0 和 xi 的差异小于一个很小的值如 1e-7则停止迭代。更新将 x0 更新为 xi。返回将 x0 转换为整数并返回。
这两种方法都能有效地计算 x 的平方根并且二分查找法的时间复杂度为 O(log x)牛顿迭代法的时间复杂度为 O(log x)。你可以根据需要选择其中一种方法。
当然使用图示和例子可以更直观地理解二分查找算法在计算平方根整数部分的过程。
例子计算 10 的平方根的整数部分
我们以计算 10 的平方根为例来展示整个过程。
步骤 1初始化
left 1right 10ans 0
步骤 2开始二分查找 第一次迭代 计算中点 mid left (right - left) / 2 1 (10 - 1) / 2 5检查 mid * mid 和 x 的关系5 * 5 2525 10因此更新 right 为 mid - 1即 right 4图示搜索区间: [1, 10]
mid 5, 5*5 10, 更新right 4第二次迭代 计算中点 mid left (right - left) / 2 1 (4 - 1) / 2 2检查 mid * mid 和 x 的关系2 * 2 44 10因此更新 ans 为 mid并更新 left 为 mid 1即 left 3图示搜索区间: [1, 4]
mid 2, 2*2 10, 更新left 3, ans 2第三次迭代 计算中点 mid left (right - left) / 2 3 (4 - 3) / 2 3检查 mid * mid 和 x 的关系3 * 3 99 10因此更新 ans 为 mid并更新 left 为 mid 1即 left 4图示搜索区间: [3, 4]
mid 3, 3*3 10, 更新left 4, ans 3第四次迭代 计算中点 mid left (right - left) / 2 4 (4 - 4) / 2 4检查 mid * mid 和 x 的关系4 * 4 1616 10因此更新 right 为 mid - 1即 right 3图示搜索区间: [4, 4]
mid 4, 4*4 10, 更新right 3结束循环
当 left right 时退出循环此时 ans 保存的就是最大的满足条件的整数。最终结果为 ans 3所以 10 的平方根的整数部分是 3。
代码对应的流程
初始化 left、right 和 ans在每次迭代中计算 mid 并比较 mid * mid 和 x 如果 mid * mid 小于等于 x则更新 ans 并右移 left如果 mid * mid 大于 x则左移 right 循环结束后返回 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这样通过二分查找我们成功找到并返回了 10 的平方根的整数部分 3。
