0069.x的平方根
难度：🟢 简单
标签：数学、二分查找
链接：69. x 的平方根
题目描述
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意： 你不可以使用任何内置指数函数，比如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
解题思路
核心思想
本题要求解一个非负整数 x 的平方根，并取其整数部分。这个问题可以转化为：寻找一个最大的整数 k，使得 k * k <= x。由于 k 的取值范围（从 0 到 x）是单调有序的，因此非常适合使用 二分查找 算法来解决。
思路选择
二分查找 是解决此问题的最优思路。我们在 [0, x] 的区间内进行搜索，不断地将搜索区间减半，来逼近最终的答案。
关键步骤
初始化指针：定义搜索区间的左右边界，
left = 0，right = x。循环条件：当
left <= right时，表示搜索区间有效，持续循环。计算中间点：计算中间值
mid。为了防止整数溢出，使用mid = left + Math.floor((right - left) / 2)。比较与收缩区间： a. 计算
mid * mid的值。 b. 如果mid * mid恰好等于x，那么mid就是我们要找的整数平方根，直接返回mid。 c. 如果mid * mid小于x，说明mid可能是答案，但我们还想尝试更大的值，所以收缩左边界：left = mid + 1。 d. 如果mid * mid大于x，说明mid太大了，它肯定不是答案，所以收缩右边界：right = mid - 1。返回结果：循环结束时（
left > right），right指针指向的就是满足k*k <= x的最大整数k，返回right。
代码实现
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function (x) {
let left = 0, right = x;
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
let curSqrt = mid * mid;
if (curSqrt === x) {
return mid;
} else if (curSqrt < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
};
复杂度分析
时间复杂度：O(log x) 二分查找每次都将搜索范围缩小一半，所以时间复杂度是关于
x的对数级别。空间复杂度：O(1) 我们只使用了常数个额外变量，空间消耗是恒定的。
相关题目
总结
本题是二分查找算法的一个经典应用。它将一个数学问题巧妙地转化为了一个在有序区间内查找特定值的问题。解题的关键在于正确地设置搜索边界，并理解循环结束时为什么返回 right 是正确答案。