平方根函数实现

问题

不使用内置的 Math.sqrt()，实现一个计算平方根的函数。

解答

方法一：二分查找

/**
 * 二分查找法求平方根
 * @param {number} x - 非负数
 * @param {number} precision - 精度，默认 1e-7
 * @returns {number} 平方根
 */
function sqrt(x, precision = 1e-7) {
  // 处理边界情况
  if (x < 0) return NaN;
  if (x === 0 || x === 1) return x;

  let left = 0;
  let right = x < 1 ? 1 : x; // x < 1 时，sqrt(x) > x

  while (right - left > precision) {
    const mid = (left + right) / 2;
    const square = mid * mid;

    if (square === x) {
      return mid;
    } else if (square < x) {
      left = mid;
    } else {
      right = mid;
    }
  }

  return (left + right) / 2;
}

// 测试
console.log(sqrt(4));    // 2
console.log(sqrt(2));    // 1.4142135...
console.log(sqrt(0.25)); // 0.5

方法二：牛顿迭代法

/**
 * 牛顿迭代法求平方根
 * 原理：求 f(x) = x² - n = 0 的根
 * 迭代公式：x_{n+1} = x_n - f(x_n) / f'(x_n) = (x_n + n / x_n) / 2
 */
function sqrtNewton(x, precision = 1e-7) {
  if (x < 0) return NaN;
  if (x === 0) return 0;

  let guess = x;

  // 迭代直到收敛
  while (Math.abs(guess * guess - x) > precision) {
    guess = (guess + x / guess) / 2;
  }

  return guess;
}

// 测试
console.log(sqrtNewton(4));    // 2
console.log(sqrtNewton(2));    // 1.4142135...
console.log(sqrtNewton(9));    // 3

方法三：整数平方根（LeetCode 69）

/**
 * 求整数平方根，只返回整数部分
 * @param {number} x - 非负整数
 * @returns {number} 平方根的整数部分
 */
function mySqrt(x) {
  if (x < 2) return x;

  let left = 1;
  let right = Math.floor(x / 2);

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const square = mid * mid;

    if (square === x) {
      return mid;
    } else if (square < x) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  // 返回 right，因为循环结束时 right < left
  // right 是最大的满足 right² <= x 的整数
  return right;
}

// 测试
console.log(mySqrt(4));  // 2
console.log(mySqrt(8));  // 2 (实际是 2.828...)
console.log(mySqrt(16)); // 4

关键点

• 二分查找：在 [0, x] 范围内查找，注意 x < 1 时上界应为 1
• 牛顿迭代：公式 guess = (guess + x / guess) / 2，收敛速度快
• 精度控制：浮点数比较要设置精度阈值，不能直接用 ===
• 边界处理：负数返回 NaN，0 和 1 直接返回
• 整数版本：循环结束后返回 right，它是满足条件的最大整数