LeetCode 69 - x 的平方根（Sqrt(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...，由于返回类型是整数，小数部分将被舍去。

约束条件

$0 \leq x \leq 2^{31} - 1$

核心要求

返回值必须是不超过真实平方根的最大整数
不能使用内置的平方根函数
需要处理边界情况和整数溢出

解题思路

这道题目的核心是要找到不超过真实平方根的最大整数。我们可以把这个问题转化为：在 [0, x] 范围内，找到最大的整数 mid，使得 mid² ≤ x。

核心洞察

关键洞察：这是一个典型的查找问题，而且搜索空间具有单调性：

如果 mid² > x，那么答案一定在 [0, mid-1] 范围内
如果 mid² ≤ x，那么 mid 可能是答案，但更大的答案可能在 [mid+1, x] 范围内

这种单调性质使得我们可以使用二分查找来解决。

算法步骤

初始化搜索范围：left = 0, right = x
二分查找过程：
- 计算中点：mid = (left + right) / 2
- 比较 mid² 与 x 的关系：
  - 如果 mid² = x：找到精确平方根，直接返回 mid
  - 如果 mid² > x：答案在左半部分，right = mid - 1
  - 如果 mid² < x：答案可能是 mid 或在右半部分，left = mid + 1
返回结果：当 left > right 时，返回 right

为什么返回 right？

当二分查找结束时，有 left > right。此时：

right 是最大的满足 mid² ≤ x 的整数
left 是最小的满足 mid² > x 的整数

由于我们要找的是不超过真实平方根的最大整数，所以应该返回 right。

实现细节

边界情况处理

x = 0：平方根为 0
x = 1：平方根为 1
大数情况：注意 mid * mid 可能会整数溢出

算法执行示例

以 x = 8 为例，展示算法执行过程：

初始：left = 0, right = 8

第一轮：mid = 4, 4² = 16 > 8
        → right = 3, left = 0

第二轮：mid = 1, 1² = 1 < 8  
        → left = 2, right = 3

第三轮：mid = 2, 2² = 4 < 8
        → left = 3, right = 3

第四轮：mid = 3, 3² = 9 > 8
        → right = 2, left = 3

结束：left > right，返回 right = 2

代码实现

func mySqrt(x int) int {
    left, right := 0, x
    for left <= right {
        mid := (left + right) / 2
        if mid*mid == x {
            return mid        // 找到精确平方根
        } else if mid*mid > x {
            right = mid - 1   // 答案在左半部分
        } else {
            left = mid + 1    // 答案在右半部分或就是mid
        }
    }
    
    return right             // 返回不超过平方根的最大整数
}

代码关键点

搜索范围：[0, x] 包含了所有可能的答案
中点计算：mid = (left + right) / 2 避免了溢出问题
三分支判断：精确匹配、过大、过小三种情况
返回策略：返回 right 确保得到正确的整数部分

复杂度分析

时间复杂度

$$T(n) = O(\log x)$$

分析过程：

每次迭代都将搜索范围缩小一半
搜索范围从 x 开始，每次除以 2
最多需要 $\log_2 x$ 次迭代

空间复杂度

$$S(n) = O(1)$$

只使用了常数个额外变量（left, right, mid），空间使用不随输入规模增长。

方法比较

方面	二分查找法	牛顿迭代法	暴力枚举
时间复杂度	$O(\log x)$	$O(\log x)$	$O(\sqrt{x})$
空间复杂度	$O(1)$	$O(1)$	$O(1)$
实现难度	★★★☆☆	★★★★☆	★★☆☆☆
稳定性	很稳定	需要处理精度问题	很稳定
推荐度	★★★★★	★★★★☆	★★☆☆☆

扩展思考

优化思路

搜索范围优化：对于较大的 x，可以将右边界设为 min(x, 46340)，因为 46340² 接近 2³¹-1
牛顿迭代法：使用 $x_{n+1} = \frac{1}{2}(x_n + \frac{a}{x_n})$ 可以更快收敛

关键收获

算法思想

二分查找的本质：在单调区间内快速定位目标值
问题转化：将开方问题转化为查找问题
边界处理：理解为什么返回 right 而不是 left

实现技巧

避免溢出：使用除法而不是乘法来比较大小
循环不变量：维护 right 是满足条件的最大值
边界情况：特别注意 x = 0 和 x = 1 的处理

常见陷阱

返回值错误：容易混淆应该返回 left 还是 right
整数溢出：mid * mid 可能超出 int 范围
边界处理：忘记处理 x = 0 的特殊情况

这道题是二分查找在数学问题中的经典应用，掌握了这个模板，就能解决一大类类似的查找问题。

Adrian Wang's blog