[路飞]_leetcode-69-x 的平方根

「这是我参与2022首次更文挑战的第26天，活动详情查看：2022首次更文挑战」

[题目地址][B站地址]

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意： 不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入： x = 4
输出： 2
复制代码

示例 2：

输入： x = 8
输出： 2
解释： 8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
复制代码

提示：

• 0 <= x <= 231 - 1

解题思路

因为本题不允许使用指数函数的算符，所以我们没有办法通过将 x 开发然后对结果向下取整的方式解题。

这里我们转换一下思路，我们可以找到第一个平方后的结果大于 x 的整数，而它 -1 就是本题要求的算术平方根。

而且基于数学知识，我们知道，一个非负整数的算术平方根必然是大于等于 0 而且小于等于它自己的，所以本题的结果必然是在 0~x 之间。

又因为从 0~x 之间的整数是单调递增的，所以我们可以利用二分查找第一个平方结果大于 x 的数字，而目标值就是该数字 -1。

这里有一个需要注意的点是当 x = 0 或者 x = 1 时，无法通过二分查找获取正确的结果。

以 x = 1 为例，第一次查找之后虽然 mid*mid<=x，但是因为 l=r，所以二分查找会结束，此时 l = r = 1，返回 -1 后的结果为 0，所以我们要对 1 进行特殊判断，当 x = 1 时，直接返回 1 即可。

代码实现

var mySqrt = function(x) {
  // 特殊判断 0 和 1
  if(x===0 || x===1) return x;
  // 因为已经特判了 0 1，所以左边界设置为1，右边界为 x
  let l = 1,r = x;
  // 二分查找第一个平方结果大于 x 的整数
  while(l<r){
    const mid = Math.floor((l+r)/2);
    if(mid*mid<=x) l = mid+1
    else r = mid;
  }
  // 返回该数字-1的结果，即为 x 的算术平方根
  return l-1;
};
复制代码

至此我们就完成了 **leetcode-69-x 的平方根 **

如有任何问题或建议，欢迎留言讨论！👏🏻👏🏻👏🏻