二分查找
解题思路
找到
mid * mid <= x的最大 mid；由于 x 的一半的平方总大于 x，则可以减小范围，减少判断范围；
如果
mid * mid === x直接返回 mid 即可，否则无论最后是执行的left = mid + 1还是right = mid - 1，left^2 一定大于 x ，则结果是left - 1；
复杂度
-
时间复杂度：
O(logx) -
空间复杂度：
O(1)
代码实现
var mySqrt = function (x) {
let left = 0;
let right = x / 2 + 1; // 直接干掉 x 的一半，减小范围
while (left <= right) {
let mid = (left + right) >>> 1;
if (mid * mid === x) {
return mid;
}
if (mid * mid < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// 执行到这里说明，x 的平方根不是一个整数
// 无论最后是执行的 left = mid + 1 还是 right = mid - 1，left^2 一定大于 x，则结果是 left - 1
return left - 1;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
1588.所有奇数长度子数组的和
上一篇
评论
