69. x 的平方根

发表于 分类于 阅读次数：

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

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

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

示例 1：

1
2
输入：x = 4
输出：2

示例 2：

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

代码实现:循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  let i = 0;
  while (i <= x) {
    if (i * i > x) {
      return i - 1;
    } else if (i * i == x) return i;
    i++;
  }
  return x;
};

代码实现:二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var mySqrt = function (x) {
  let l = 0,
    r = x;
  ans = -1;
  while (l <= r) {
    let mid = (l + (r - l) / 2) >> 0;
    if (mid * mid <= x) {
      ans = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return ans;
};