69. x 的平方根
给你一个非负整数 x
,计算并返回 x
的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
**注意:**不允许使用任何内置指数函数和算符,例如 pow(x, 0.5)
或者 x ** 0.5
。
示例 1:
输入:x = 4
输出:2
示例 2:
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
提示:
0 <= x <= 231 - 1
解题思路
示例 2 中,从”小数部分被舍去”可知,这是在求二分法的下界
因此,可以使用二分查找来解题
function mySqrt(x: number): number {
// 定义左边界(下界)
let l = 0;
// 定义右边界(上界)
let r = x;
// 这里取等,是因为题目范围是个闭区间
while (l <= r) {
// 当收缩范围直到只有两个数时,左边界不确定,因此借助r*r > x来判断我们需要的数
if (r - l <= 1) {
return r * r > x ? l : r;
}
// 定义中间值
let mid = l + Math.floor((r - l) / 2);
// 这道题求下界,代表着当mid*mid < x时,我们无法确定左边界,因此直接使用mid来模糊确定左边界
// 而当mid*mid > x时,我们能直接收缩右边界的范围,是因为符合mid*mid > x的数并不是需要的数
// 因此,我们可以直接收缩右边界范围
// 当然,如果mid*mid == x时,就代表找到了符合的数,直接返回即可
if (mid * mid > x) {
r = mid - 1;
} else if (mid * mid == x) {
return mid;
} else {
l = mid;
}
}
return -1;
}
另外,这道题还可以进行变形
也即是:将问题变成求上界
比如当 x = 8 时,x 的平方根大约是 2.8,那我们的答案就是 3,也就是求上界
function myUpperSqrt(x: number): number {
// 定义左边界(下界)
let l = 0;
// 定义右边界(上界)
let r = x;
while (l <= r) {
if (r - l <= 1) {
// 当收缩范围直到只有两个数时,右边界不确定,因此借助l*l > x来判断我们需要的数
return l * l > x ? l : r;
}
// 相当于 let mid = l + Math.floor((r - l) / 2)
let mid = l + ((r - l) >> 1);
/**
* 同样的思路,右边界不确定,借助mid来模糊确定右边界
* 左边界确定,直接收缩左边界范围即可
*/
if (mid * mid > x) {
r = mid;
} else if (mid * mid == x) {
return mid;
} else {
l = mid + 1;
}
}
return -1;
}