69. x 的平方根
题目：
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
总结：逻辑是一样的，找到区间 [i, i+1)
// 方法一：执行时长稍长，但内存占用小
function sqrt(x) {
const mid = Math.ceil(x/2); // 优化点
let i = 0;
for(; i < mid; i++) {
if ((i * i <= x) && ((i + 1) * (i + 1) > x)) { // 注意这里要给 = 号，否则会遗漏
return i;
}
}
return i
};
// 方法二 开区间 (left, right)：执行时间短，但内存占用大点儿
function mySqrt3(x) {
let left = 0, right = Math.min(x + 1, 46341);
while (left + 1 < right) {
// 循环不变量：left^2 <= x && right^2 > x
let m = Math.floor((left + right) / 2);
if (m * m <= x) {
left = m;
} else {
right = m;
}
}
// 循环结束时得到 left+1 == right，此时 left^2 <= x 且 right^2 > x
return left; // 所以 left 最大的满足 m^2 <= x 的数
};
解答：
- 方法一：遍历
平方根 <= x/2，取 x 的一半(取向上靠近的整数)
时间复杂度：O(n)，空间复杂度：xx
var mySqrt = function(x) {
const mid = Math.ceil(x/2);
let i = 0;
for(; i < mid; i++) {
// 注意这里要给 = 号，否则会遗漏
if ( (i * i <= x) && ((i + 1) * (i + 1) > x)) {
return i;
}
}
return i
};
- 方法二：二分法
时间复杂度：O(logx) - 每一次搜索的区间大小为原来的 1/2，空间复杂度：O(1)
逻辑：将要查找的值划分在区间 [left, right) 中，通过两者的中间值 mid 与 x 的比较来判断求解的结果在哪个区间，直到最后找到对应结果
let mySqrt = (x) => {
if (x === 0) {
return 0;
}
let left = 0, right = x;
let mid = Math.ceil(x / 2);
while(left < right) {
// 不用乘法，防止溢出
if (x / mid === mid) {
return mid;
}
if (x / mid < mid) {
// 注意 ⚠️ ：通过判断条件已知 mid^2 大于 x
right = mid - 1;
} else {
left = mid;
}
mid = Math.ceil((left + right) / 2);
}
return left
}