69.x 的平方根(力扣LeetCode)
题目描述
给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1:
示例 2:
提示:
- 0 <= x <= 2 - 1
浮点数二分
// 定义解决问题的类 Solution
class Solution {
public:
// 计算并返回非负整数 x 的算术平方根的整数部分
int mySqrt(int x) {
// 由于要找的平方根不会超过 x 本身,二分查找的起始范围设定为 [0,x]
double l = 0, r = x;
// 使用二分查找来逼近平方根的值。这里设置一个很小的阈值 1e-6,
// 表示当左右边界的差距小于这个阈值时停止搜索,
// 这是因为我们只需要得到整数部分
while (r - l >= 1e-6) {
// 计算中点值
double mid = (l + r) / 2.0;
// 如果 mid 的平方大于或等于 x,我们知道平方根位于左半部分,
// 所以将右边界移动到 mid
if (mid * mid >= x) r = mid;
// 如果 mid 的平方小于 x,我们知道平方根位于右半部分,
// 所以将左边界移动到 mid。这里不需要处理边界问题,
// 因为我们不是在寻找具体的元素,而是逼近一个实数值
else l = mid;
}
// 最后返回右边界 r 作为结果,由于题目要求只要整数部分,
// 变量 r 会自动转换为 int 类型,并且舍去小数部分
return r;
}
};