69. x 的平方根
实现 int sqrt(int x)
函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数,小数部分将被舍去。
思路
二分法找到左边临界点
代码
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {
let left = 0, right = x;
for(let i = 0; i < x; i ++) {
let mid = left + right >> 1;
let doubleMid = mid ** 2;
if(doubleMid <= x && (mid + 1) ** 2 > x) {
return mid;
} else if (doubleMid > x) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
};
复杂度分析
时间复杂度 #card=math&code=O%28logN%29)
空间复杂度 #card=math&code=O%281%29)