如果二分查找超出边界了,无论最后的边界是停留在小于 x 的位置还是大于 x 的位置,都返回 ans 即可,因为它是最后一个乘积小于 x 的值,一定是正确答案。
/**
* @param {number} x
* @return {number}
*/
let mySqrt = function (x) {
let left = 0;
let right = x;
let ans = -1;
while (left <= right) {
let mid = Math.round((left + right) / 2);
let product = mid * mid;
if (product <= x) {
ans = mid;
left = mid + 1;
} else if (product > x) {
right = mid - 1;
} else {
return mid;
}
}
return ans;
};
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
示例 2:
思路
本题利用二分查找来求解,一开始把右边界粗略的设定为目标值 x,左右边界的中间值设为 mid,然后在二分过程中每次发现 mid * mid < x 的情况,就把这个 mid 值记录为 ans。
如果计算出的乘积正好等于 x,就直接返回这个 mid 值。
如果二分查找超出边界了,无论最后的边界是停留在小于 x 的位置还是大于 x 的位置,都返回 ans 即可,因为它是最后一个乘积小于 x 的值,一定是正确答案。