#69. x 的平方根

LeetCode 原题链接

#题目描述

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

由于返回值是整数，结果只保留整数部分，小数部分会被舍去。也就是说，要返回最大的整数 k，使得：

k * k <= x

示例：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.828...，去掉小数部分后返回 2。

#题型判断

这是一道答案二分题。

我们不是在数组中查找某个元素，而是在可能的答案范围里查找最大的合法整数。对于任意整数 mid：

• 如果 mid * mid <= x，说明 mid 是合法答案，但可能还有更大的合法答案。
• 如果 mid * mid > x，说明 mid 太大了，mid 以及右边的数都不可能是答案。

合法性随着数字变大呈现单调变化：先合法，后不合法。因此可以用二分查找。

#核心思路

要找的是最大的整数平方根，也就是最后一个满足 mid * mid <= x 的整数。

如果 x < 2，答案就是 x 本身，可以直接返回。

当 x >= 2 时，搜索范围可以定为 [1, x]：

• 1 一定是下界。
• x 一定是上界，虽然当 x > 1 时答案不会超过 x / 2，但 [1, x] 更直观，复杂度仍然是 O(log x)。

每次取中间值 mid：

1. 如果 mid <= x / mid，等价于 mid * mid <= x，说明 mid 合法，先记录 ans = mid，再去右半边找更大的合法值。
2. 如果 mid > x / mid，等价于 mid * mid > x，说明 mid 太大，右侧也都太大，去左半边继续找。

这里使用 mid <= x / mid，而不是直接写 mid * mid <= x，主要是为了避免在一些语言中整数乘法溢出。JavaScript 的 Number 对这道题限制通常可以直接相乘，但这种写法更通用。

#示例步骤图解

以 x = 8 为例，目标是找到最大的 k，使得 k * k <= 8。

此时 left = 3，right = 2，搜索区间为空，返回最后记录的合法答案 ans = 2。

可以把整个过程理解成：

候选答案：0 1 2 3 4 5 6 7 8
合法性：  T T T F F F F F F
答案：        ^
             最后一个合法位置

#变量与区间含义

本题使用闭区间 [left, right]。

• left：当前可能答案范围的左边界。
• right：当前可能答案范围的右边界。
• mid：当前检查的候选平方根。
• ans：当前已经找到的最大合法答案。

初始化：

let left = 1;
let right = x;
let ans = 0;

ans 初始化为 0，表示还没有找到合法答案。由于 x >= 2 时 1 一定合法，循环中会更新 ans。

#推进规则

当前 mid 是否可能成为答案？

• 当 mid <= x / mid 时，mid * mid <= x，mid 可能成为答案。
• 当 mid > x / mid 时，mid * mid > x，mid 不可能成为答案。

边界移动：

• mid <= x / mid：说明 mid 合法，记录 ans = mid，并尝试更大的数，所以 left = mid + 1。
• mid > x / mid：说明 mid 太大，排除 mid 和右侧，所以 right = mid - 1。

循环结束后，ans 就是最后一个满足 k * k <= x 的整数。

#边界条件与易错点

• x = 0：直接返回 0。
• x = 1：直接返回 1。
• 不能遇到 mid * mid < x 就直接返回，因为还要找更大的合法整数。
• 不能返回 left，循环结束时 left 通常已经越过了最后一个合法位置。
• 使用闭区间时，边界更新必须是 mid + 1 和 mid - 1，否则可能死循环。
• 在 Java、C++ 等语言中，mid * mid 可能溢出，可以用 mid <= x / mid 来判断。

#代码实现

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  if (x < 2) {
    return x;
  }

  let left = 1;
  let right = x;
  let ans = 0;

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

    if (mid <= x / mid) {
      // mid 的平方不超过 x，mid 是一个合法答案。
      ans = mid;
      // 继续向右找，看看是否存在更大的合法答案。
      left = mid + 1;
    } else {
      // mid 的平方超过 x，mid 和右侧都不可能是答案。
      right = mid - 1;
    }
  }

  return ans;
};

#复杂度分析

• 时间复杂度：O(log x)。每次二分都会把候选答案范围缩小一半。
• 空间复杂度：O(1)。只使用了几个变量。