二分法求解平方根的“陷阱”

冷不防 2022-08-12 17:00 202阅读 0赞

对于一个整数求解其平方根可以使用“二分法”和“牛顿法”。

所谓“二分法”就是不断地缩小平方根所在的范围，直到收敛到一个数。例如求解数k的平方根t，首先设置t的范围为\[left, right\](其中left和right分别初始化为1， k)，然后判断m=(l+k)/2与k的平方根t的关系，如果m比t小，则t的范围为\[m+1， right\]，否则为\[left, m-1\]，然后依次循环，直到left>=right终止。

相比较于“牛顿法”，“二分法”比较直观，简单，而且通过程序极易实现，程序核心代码如下：

**int left = 1, right = k;**

**int root = 0;**

**while(left < right) \{**

**int mid = (left + right) / 2;**

**if(mid == k / mid) \{**

**return mid;**

**\} else if (mid > k / mid) \{**

**right = mid - 1;**

**\} else \{**

**left = mid + 1;**

**root = mid; //不能完全开方是找到平方根的整数部分**

**\}**

**\}**

通过观察代码，我们可以发现其中有两处地方值得考虑（代码中红线标出的部分），对于第一处判断可能很多人潜意识的会写成**“mid \* mid == k”**，而第二处写成**“****mid \* mid > k****”**，初看，这个貌似的确没有什么问题，但是在运行程序时可能会发现出现**死循环**现象。

为什么会出现这种情况呢？

主要是因为在计算机中整型数据（int）是有位数限制的，一般是4个字节（32bits），这就可能出现“mid \* mid”溢出的情况，这样在程序执行过程中就可能出现无限循环的情况。

因此，**以后在程序设计过程中一定要特别注意不同类型数的位数的限制，避免因为溢出造成的逻辑错误，而且在能够同时使用乘法或者除法（注意考虑除数不能为0）时，尽量使用除法计算。**

**非常感谢xuqing-ict指出的问题，在做运算时，不仅要避免乘法可能会带来的问题，还需要考虑到加法可能或造成的溢出问题，对于“二分法”算法中求解"mid=left+right"就需要考虑右边可能因为溢出造成的结果错误，因此应该改成"mid=left+(right-left)/2".**

发表评论取消回复

表情：

评论列表（有 0 条评论，202人围观）

还没有评论，来说两句吧...

相关阅读

相关 x 的平方根

题目给你一个非负整数 x ，计算并返回 x 的算术平方根。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。注意：不允许使用任何内置指数函数

àì夳堔傛蜴生んèń/ 2024年04月08日 13:15/ 0 赞/ 88 阅读

相关二分查找求解x的平方根

题目描述：实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

╰半橙微兮°/ 2022年12月28日 04:25/ 0 赞/ 73 阅读

相关 P06 X的平方根(二分法、牛顿迭代)

求X的平方根的整数部分方法一：二分法 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aH

迈不过友情╰/ 2022年10月13日 05:17/ 0 赞/ 221 阅读

相关【经典面试题三】x的平方根的两个解法（二分法，牛顿迭代）

题目在不使用sqrt(x)函数的情况下，得到x的平方根的整数部分 > 例1： > 输入：24 > 输出：4 > > 例2： > 输入：25 > 输出

男娘i/ 2022年09月12日 02:56/ 0 赞/ 221 阅读

相关力扣-69题 x的平方根（C++）- 二分法，有值得注意的小tip

题目链接：[https://leetcode-cn.com/problems/sqrtx/][https_leetcode-cn.com_problems_sqrtx] 题

╰半夏微凉°/ 2022年09月03日 05:25/ 0 赞/ 92 阅读

相关二分法求解平方根的“陷阱”

对于一个整数求解其平方根可以使用“二分法”和“牛顿法”。所谓“二分法”就是不断地缩小平方根所在的范围，直到收敛到一个数。例如求解数k的平方根t，首先设置t的范围为\[lef

冷不防/ 2022年08月12日 17:00/ 0 赞/ 203 阅读

相关二分法求解方程的值 matlab

首先定义一个二分求根的函数： function root=bisect(fun,a,b,eps) n=1+round((log(b-a)-log(ep

柔光的暖阳◎/ 2022年07月26日 00:21/ 0 赞/ 44 阅读

相关遍历和二分法求解二维数组中查找问题

/ Created by cuboo on 2017/4/20. 问题：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到

深碍√TFBOYSˉ_/ 2022年06月17日 07:29/ 0 赞/ 173 阅读

相关二分法求解最大最小值模板

二分法题解：[https://www.cnblogs.com/hyl2000/p/5734908.html][https_www.cnblogs.com_hyl2000_p_5

Love The Way You Lie/ 2022年05月14日 04:19/ 0 赞/ 237 阅读

相关通过梯度下降和牛顿法求解一个数的平方根

梯度下降梯度下降法（Gradient descent）是一个一阶最优化算法，就是让参数沿着损失函数负梯度的方向更新。迭代的步长，也就是学习率是事先给定的，如果负梯度的绝

柔光的暖阳◎/ 2022年01月28日 03:49/ 0 赞/ 353 阅读