LeetCode 69. x 的平方根

◎

本节目标

用二分边界求非负整数的向下取整平方根，并避开乘法溢出。

查看原题

返回数学建模框架

题意与约束

给定非负整数 x，返回 ⌊√x⌋。答案属于 32 位整数范围，但中间平方未必安全。

第一反应与瓶颈

从 0 递增试探直到平方超过 x 可行，却需要 O(√x) 次。平方越大越接近极限，越不应直接相乘比较。

数学关系与算法推导

谓词 m² ≤ x 随 m 单调：小于等于答案的全部为真，之后全为假。在 [0, x] 二分最大的真值；用 m ≤ x / m 等价判断，避免 m * m 溢出。

正确性依据

循环始终保留已知可行的 answer，并只在 mid 可行时把左边界移到其右侧；不可行时删去 mid 及右侧。区间空时，answer 是所有可行整数中的最大者，正是向下取整平方根。

样例执行过程

x = 8 时，中点依次把可行答案更新到 2；检查到 3 时 3 > 8 / 3，右边界左移，最终返回 2。

代码实现

C++

C++17

#include <algorithm>
using namespace std;

class Solution {
public:
    int mySqrt(int x) {
        int left = 0;
        int right = x;
        int answer = 0;
        while (left <= right) {
            const int mid = left + (right - left) / 2;
            if (mid == 0 || mid <= x / mid) {
                answer = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return answer;
    }
};

Python

Python 3

class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x
        answer = 0
        while left <= right:
            mid = left + (right - left) // 2
            if mid == 0 or mid <= x // mid:
                answer = mid
                left = mid + 1
            else:
                right = mid - 1
        return answer

复杂度分析

• 时间复杂度：O(log x)。
• 空间复杂度：O(1)。

边界与易错点

• x = 0 时中点为零，必须避免除以零。
• 不用 sqrt 的浮点结果作循环边界，避免精度和转换边界问题。
• 不直接写 mid * mid <= x。

模式迁移

“最大满足条件的整数”是二分边界题的原型；可迁移到开方、容量、速度和最小可行答案等单调判定问题。