x 的平方根

LeetCode 69：在整数候选区间内用二分查找得到平方根的整数部分。

LeetCode 69 简单数组

发布于 2026.10.14 约 2 分钟阅读浏览 — 次

二分查找
数学
复杂度
Python
变量

题目：69. x 的平方根

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

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

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

示例 1：

输入： x = 4
输出： 2

示例 2：

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

1. 查找过程

以 x = 8 为例，要找的是 平方不超过 8 的最大整数。非负整数越大，平方越大，可以用二分查找缩小范围。

下面是区间示意：k 表示候选整数，k² 表示它的平方；L、M、R 对应代码中的 l、mid、r。

第 1 轮：检查 [0, 7]

代码块 Text

1
2
3
4
k:   0  1  2  3  4  5  6  7
k²:  0  1  4  9 16 25 36 49
     ●──●──●──●──●──●──●──●
     L        M           R

mid = 3，3 * 3 = 9 > 8。3 已经太大，右侧的数也都太大。

更新 r = mid - 1，得到 r = 2，剩下 [0, 2]。

第 2 轮：检查整数 [0, 2]

代码块 Text

1
2
3
4
k:   0  1  2
k²:  0  1  4
     ●──●──●
     L  M  R

mid = 1，1 * 1 = 1 < 8。1 满足条件，但右侧可能还有更大的答案。

更新 l = mid + 1，得到 l = 2，只剩 2。

第 3 轮：只检查整数 2

代码块 Text

1
2
3
4
k:    2
k²:   4
      ●
    L=M=R

mid = 2，2 * 2 = 4 < 8，继续向右找：l = mid + 1，得到 l = 3。

此时 l > r，结束查找。两侧边界停在这里：

代码块 Text

1
2
3
4
k:    2     3
k²:   4     9
      R     L
    4 < 8 < 9

2 的平方没超过 8，再大一个整数 3 就超过了，所以返回 r = 2。

2. Python 实现

num 对应题目中的 x。当 num >= 2 时，整数平方根小于 num，右边界可以取 num - 1。

代码块 Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def sqrt(num):
    l, r = 0, num - 1

    while l <= r:
        mid = l + (r - l) // 2
        if mid * mid > num:
            r = mid - 1  # mid 及其右侧整数的平方都太大
        elif mid * mid < num:
            l = mid + 1  # mid 满足条件，继续找右侧是否有更大的答案
        else:
            return mid  # 平方恰好相等，直接返回

    # 初始区间没有包含 0、1 的答案，单独处理：
    # num = 0：不进循环，l = 0；num = 1：检查 0 后，l = 1
    if num <= 1:
        return l
    return r  # 未精确命中时，r 是平方不超过 num 的最大整数


print(sqrt(8))
print(sqrt(4))
print(sqrt(1))
print(sqrt(0))

运行结果 Text

3. 复杂度

时间复杂度：O(log x)，每轮将整数候选区间缩小约一半。
额外空间复杂度：O(1)，只维护固定数量的整数变量。

使用 GitHub 登录后参与讨论，评论将公开保存在 GitHub。

阅读到这里时加载评论。