README.md

Sqrt(x)

难度：简单

https://leetcode-cn.com/problems/sqrtx/

题目

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

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

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

示例

示例 1：

输入：x = 4
输出：2

示例 2：

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

解法

二分法

/**
 * 二分法
 * @desc 时间复杂度 O(logN)   空间复杂度 O(1)
 * @param x {number}
 * @return {number}
 */
export function mySqrt(x: number): number {
  let left = 0;
  let right = x;
  let ans = -1;

  while (left <= right) {
    const mid = (right + left) >> 1;
    if (mid * mid <= x) {
      ans = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return ans;
}

牛顿迭代

牛顿迭代法 是一种可 以用来快熟求解函数零点的方法。

为了叙述方便，我们用C表示待求出平方根的那个整数。显然C的平方根就是函 数y=f(x)=x^2-C的零点。

牛顿迭代法的本质是借助泰勒级数，从初始值开始快熟向零点逼近。我们任取一个x0作为 初始值，在每一步的迭代中，我们找到函数图像上的点(xi,f(xi))，过该点做一条斜率为 该点导数f'(xi)的直线，与横轴的交点记为xi+1。xi+1相较于xi而言距离零点更近 。在经过多次迭代后，我们就可以得到一个距离零点非常接近的交点。下图给出了从x0开 始迭代两次，得到x1和x2的过程。

接下来，我们可以来研究xi和xi-1的关系。当我们已知了x0的时候，此时 的y=f(x)=x^2-C的坐标点为(x0, x0^2 - C)，然后f'(x)=2x，因此该点的导数 为2x0，因此直线的函数为y = 2x0 · x + b。

然后我们就需要求b值，将(x0, x0^2 - C)坐标点代入 得b = (x0^2 - C) - 2x0^2 = -C - x0^2，因此我们可以求出直线函数 为y = 2x0 · x - C - x0^2。

然后我们想求x1的时候，即y=0，代入求 出x1 = (C + x0^2) / 2x0 = 0.5 * (x0 + C/x0)。

因此我们可以得知，当我们用变量t作为初始值，则t = 0.5 * (t + x / t)，然而 当t^2 - x的差距小于 1 时就可以返回结果了。

/**
 * 牛顿迭代
 * @desc 时间复杂度 O(logN)   空间复杂度 O(1)
 * @param x {number}
 * @return {number}
 */
export function mySqrt2(x: number): number {
  if (x === 0) return 0;

  let t = x;
  while (t * t - x >= 1) {
    // k = 2t
    // y = 2tx + b
    // b = (t^2 - C) - 2t^2 = - C - t^2
    // y = 2tx - C - t^2
    // x = (C + t^2) / 2t = 0.5 * (t + C/t)
    t = 0.5 * (t + x / t);
  }

  return Math.floor(t);
}