69. Sqrt(x)

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

  • For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:

1
2
3
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

1
2
3
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

Constraints:

  • 0 <= x <= 231 - 1

解法解析

计算平方根问题可以通过二分查找高效解决，时间复杂度为 O (log x)，空间复杂度为 O (1)。

核心思路

问题本质是找到最大的整数 mid 使得 mid \* mid <= x，这个整数就是 x 的平方根的整数部分。

算法步骤

特殊情况处理：当 x 为 0 或 1 时，直接返回 x 本身

设置查找边界：对于 x > 1，平方根一定在 [1, x/2] 范围内，这是因为对于 x > 4，x/2 的平方已经大于 x

二分查找过程：

  • 计算中间值mid，使用left + (right - left) / 2避免整数溢出
  • 计算mid * mid，使用long long类型防止乘法结果溢出
  • 比较平方结果与 x：
    • 若相等，直接返回 mid（找到精确的整数平方根）
    • 若小于 x，记录当前 mid 为候选结果，并向右继续查找更大的可能值
    • 若大于 x，向左查找更小的值

返回结果：循环结束后，返回记录的最大满足条件的整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
using namespace std;

class Solution {
public:
    /**
     * 使用牛顿迭代法计算非负整数x的平方根，返回整数部分
     * 牛顿迭代法是一种求解方程近似根的高效数值方法
     * @param x 非负整数
     * @return x的平方根的整数部分
     */
    int mySqrt(int x) {
        // 特殊情况处理：x为0或1时，平方根就是自身
        if (x <= 1) {
            return x;
        }
        
        // 初始猜测值，从x开始
        double guess = x;
        // 精度控制：当误差小于此值时，认为已经收敛
        double epsilon = 1e-6;
        
        // 牛顿迭代过程：不断优化猜测值，直到满足精度要求
        // 终止条件：当前猜测值的平方与x的差值小于epsilon
        while (guess * guess - x > epsilon) {
            // 牛顿迭代公式：g_{n+1} = (g_n + x/g_n) / 2
            // 该公式源自对函数f(g) = g² - x求根的切线近似
            guess = (x / guess + guess) / 2;
        }
        
        // 将结果转换为整数并返回（自动截断小数部分）
        return static_cast<int>(guess);
    }
};