69. x 的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
来源：力扣（LeetCode）
链接：https:///problems/sqrtx
class Solution {
public:
int mySqrt(int x) {
if(x==0){
return 0;
}
int l=0;
int r=x;
while(l<=r){
int mid=l+(r-l)/2;
if(mid==0) mid=1;
if(x/mid<mid){
r=mid-1;
}else if(x/mid>mid){
l=l+1;
}else{
return mid;
}
}
return r;
}
};
这段代码是一个用于计算一个非负整数的平方根的函数mySqrt。下面是对代码的中文分析以及可能出现错误的地方的解释：
-
首先，代码检查输入的整数
x是否为0。如果是0，直接返回0作为结果。 -
接下来，代码初始化两个变量
l和r，分别代表搜索范围的左右边界。初始时，左边界l为0，右边界r为输入的整数x。 -
然后，代码进入一个循环，循环条件是左边界
l小于等于右边界r。这个循环使用二分查找的思想来逼近平方根的值。 -
在每次循环中，代码计算中间值
mid，使用的是左边界l和右边界r的中点。这里采用了一种防止整数溢出的计算方式，通过l+(r-l)/2来计算中间值。 -
接下来，代码进行平方根的判断。首先，如果
mid等于0，将其设置为1。这是为了避免在下面的除法运算中出现除数为0的情况。 -
然后，代码进行除法运算，将输入的整数
x除以中间值mid并与mid比较。如果商小于中间值mid，则说明平方根位于当前中间值mid的左边，将右边界r更新为mid-1。 -
如果商大于中间值
mid，则说明平方根位于当前中间值mid的右边，将左边界l更新为l+1。 -
如果上述两个条件都不满足，说明商等于中间值
mid，即找到了平方根，直接返回中间值mid作为结果。 -
最后，当循环结束时，返回右边界
r作为最终的结果。
可能的易错点：
- 在计算中间值
mid时，采用了一种防止整数溢出的方式。这是因为当搜索范围较大时，l和r的和可能会超过整数的表示范围。使用l+(r-l)/2可以避免这个问题。 - 代码中将
mid等于0的情况特殊处理为1，是为了避免除数为0的情况。这是因为在下面的除法运算x/mid中，mid作为除数，不能为0，否则会导致运行时错误。 - 在判断平方根位置时，使用了商与中间值的比较。商小于中间值说明平方根位于当前中间值
mid的左边，将搜索范围的右边界r更新为mid-1。商大于中间值说明平方根位于当前中间值mid的右边，将搜索范围的左边界l更新为l+1。这样不断缩小搜索范围，直到找到平方根或者确定平方根在左右边界之间的某个位置。 - 最后，返回右边界
r作为结果是因为循环结束时，左边界l已经超过了右边界r，此时r保存的是最接近平方根的整数值，作为结果返回。
总结一下，该代码通过二分查找的方法在指定范围内寻找平方根，具有较高的效率。但需要注意的是边界条件的处理和防止整数溢出的情况，以及正确理解平方根位置的判断逻辑。
