69. x 的平方根(JS实现)

69. x 的平方根(JS实现)

1 题目
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数,小数部分将被舍去。

2 思路
这道题思路很简单,就是遍历所有整数,来找到目标,但由于自然整数是有序的,因此可以用二分法来加快速度

3代码
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {
if (x === 0 || x === 1) return x;
let low = 1;
let high = x;
let mid = Math.floor((low + high) / 2);
while (low <= high) {
let num1 = mid * mid;
let num2 = (mid + 1) * (mid + 1);

if (x > num2) {
low = mid + 1;
} else if (x < num1) {
high = mid – 1;
} else if (x === num2){
return mid + 1;
} else {
return mid;
}

mid = Math.floor((low + high) / 2);
}

};