69. x 的平方根
题目：
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
解答：
- 方法一：遍历
平方根 <= x/2，取 x 的一半(取向上靠近的整数)
时间复杂度：O(n)，空间复杂度：xx
var mySqrt = function(x) {
let 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
}