企业官网建设流程全解析

实话说，第一次在LeetCode上刷到第69题“x 的平方根”，我差点把它当签到题跳过——要求就那么短短一句话：实现int mySqrt(int x)，计算并返回 x 的平方根，其中 x 是非负整数，结果只保留整数部分，小数部分全部舍去。不能用内置开方函数。看起来就是二分一把梭的事，但真到了面试环节，被追问整数溢出、边界条件、迭代收敛这些细节时，能从头讲透的人其实不多。这道题好在哪？它同时踩中三个高频考点：单调性二分、整型溢出、数值迭代收敛。不管你是新手还是准备跳槽的老手，把69题吃透，等于同时复习了“二分查找边界怎么定”和“牛顿迭代怎么落地”两套基本功。这篇就顺着我自己的刷题过程，把两种主流解法从原理讲到代码，再补上测试用例和踩坑记录。

1. 题目描述与隐藏条件拆解

1.1 从题面到函数签名

题目描述核心就是一句话：给定一个非负整数 x，返回 sqrt(x) 的整数部分，向下取整。这不是让你实现一个通用数学库里的浮点开方，而是只关心整数结果。例如输入 8，输出 2；输入 9，输出 3；输入 0，输出 0。

题目给的是 C++ 风格的int mySqrt(int x)，但LeetCode 上很多语言版本都存在，你用 Java、Python、Go 写都可以。核心逻辑不依赖语言，只是不同语言对“整数溢出”“整型除法”的处理有差别，这一点后面会专门展开。

我第一次刷的时候有个误解：以为只要把浮点sqrt算出来再强转成 int 就行——题目直接禁掉了库函数，所以这条路堵死。另一个误解是“向下取整”和“四舍五入”混在一起，结果 8 的平方根是 2.828，向下取整是 2，不是 3。

1.2 三个容易被忽略的隐含条件

1. 返回类型是 int：意味着我们只找整数答案，不关心小数部分。这个约束反而降低了难度，也让二分法变得特别合适——我们要找的是一个离散的边界值，而不是一个连续点。
2. x 可以为 0 和 1：很多解法里喜欢初始化左边界为 1、右边界为 x，如果 x=0 或 x=1，代码会直接走错分支甚至除零。至少我在自己写的第一个版本里就吃过这个亏。
3. x 的最大值接近 2^31 - 1：当 x 很大时，mid * mid很容易超出 int 范围。这是 LeetCode 69 在 C++/Java 版里最经典的坑，后面会重点讲。

如果面试官继续加码，把题目改成“保留三位小数”或者“输入变成 double”，这两种解法依然成立，但退出条件要从整数比较换成精度比较。这也是我把这题拿来练手的原因：一道题能引出连续和离散两条线。

2. 二分查找解法：搜索空间、单调性与边界条件

2.1 单调性是二分的入场券

要判断一个问题能不能用二分，先问一句：搜索空间里的“答案函数”是否单调？对于平方根，目标其实是找最大的整数 t，使得 t² ≤ x。随着 t 从 0 一直增加到 x，t² 单调不减，所以所有满足 t² ≤ x 的 t 会连成一个前缀区间。比如 x=8 时：t=0、1、2 都满足，t=3 不满足，答案就是前缀区间的右端点 2。

这个性质就是二分的入场券。只要满足“前缀可行、后缀不可行”，就可以用二分快速找到最后一个可行点。相反，如果搜索空间没有单调性，二分就不能乱用。理解这一点比背模板重要得多，因为很多题换了层皮，本质还是找“单调区间的分界点”。

搜索空间也不用整个 [0, x] 都枚举，二分每次砍半，对于 int 最大值 2147483647，最多只需要 31 轮左右。这个数字后面还会提到。

2.2 mid^2 溢出的两种规避写法

这是我在这题上踩得最狠的坑。直接写if (mid * mid <= x)在绝大多数测试用例下都是正确的，唯独 x 取到接近 2^31 - 1 时会出错。原因很简单：当 mid 超过 46340 时，mid * mid 已经大于 2^31 - 1，int 装不下，会溢出成负数。负数当然小于 x，于是二分往右拐，最终得到错误答案。

规避办法有两条路：

// 写法一：把乘法改成除法，避免任何乘法溢出 if (mid <= x / mid) { ... } // 写法二：用 64 位整数存乘积 if (1LL * mid * mid <= x) { ... }

我推荐优先理解写法一。mid <= x / mid在数学上和mid * mid <= x完全等价（x 和 mid 都非负），但它的中间结果不会超过 x 的范围，天然安全，而且代码末尾不用再担心类型强行转换。在面试里写出这个判断，还能顺带解释一句“我这么写是为了防止 mid² 溢出”，这是加分项。

写法二也没问题，在 Python 里甚至不需要1LL，因为 Python 的整数是任意精度的。但在 C++/Java 里，如果你忘了把 mid 提升成 long long/long，就会掉进和第一个写法同样的坑。

2.3 循环不变量与返回值选择

二分写多了你会发现，真正难的不是“知道要用二分”，而是“循环结束后返回 l 还是 r”。我建议用下面这套不变量，逻辑清晰且不容易错：

• l的左边界表示“当前可能成为答案的最小值”
• r的右边界表示“当前可能成为答案的最大值”
• 每次取mid = l + (r - l) / 2
• 如果mid <= x / mid，说明 mid 可行，答案至少是 mid，把左边界收窄到l = mid + 1
• 否则 mid 不可行，答案小于 mid，把右边界收到r = mid - 1

循环结束条件是l > r。此时 r 指向最后一个可行点，l 指向第一个不可行点。所以最后返回 r。

为什么这里用l = mid + 1而不是l = mid？关键在于保证每次循环区间都在缩短。如果写成l = mid，在 l 和 r 相邻的时候，比如 l=2、r=3、mid=2，又满足条件，下一轮还是 l=2、r=3，就死循环了。把边界往里挪一格，区间必然缩小，这是二分模板里最核心的纪律。

2.4 完整实现与复杂度分析

把上面逻辑拼起来，C++ 版本长这样：

class Solution { public: int mySqrt(int x) { if (x < 2) return x; int l = 1, r = x; while (l <= r) { int mid = l + (r - l) / 2; if (mid <= x / mid) { l = mid + 1; } else { r = mid - 1; } } return r; } };

Python 版本几乎是同一套逻辑，只是除法要用//：

class Solution: def mySqrt(self, x: int) -> int: if x < 2: return x l, r = 1, x while l <= r: mid = (l + r) // 2 if mid <= x // mid: l = mid + 1 else: r = mid - 1 return r

时间复杂度显然是 O(log x)，空间 O(1)。对 int 范围来说，每一轮区间减半，从 x 到 1 最多 31 轮。

3. 牛顿迭代法：从切线逼近到整型收敛

3.1 切线法的几何直觉与公式推导

二分法靠的是“区间折半”，牛顿迭代法走的是另一条路：用切线去逼近方程的根。求平方根等价于解方程 f(t) = t² - x = 0。牛顿法从某个猜测值 t0 出发，在曲线 f(t) 上过点 (t0, f(t0)) 作切线，切线和横轴的交点就是下一次猜测 t1，然后重复这个过程。

切线的斜率是 f'(t0) = 2t0，切线方程写成：

t1 = t0 - f(t0) / f'(t0) = t0 - (t0² - x) / (2t0)

化简之后得到非常漂亮的递推式：

t1 = (t0 + x / t0) / 2

这个式子的直觉很好记：如果 t0 猜小了，x / t0 偏偏会偏大，两者取平均，就自动把结果往真实值方向拉。你可以把它理解成“一个说高一个说低，取个中间值”，每一步都是猜测值和真实值的算术平均加速靠近。

3.2 为什么整数版也会收敛，以及停止条件

牛顿法在实数域里是个二次收敛的过程——每一步有效数字位数大概翻倍。对于 int 范围内的 x，从初始值 x 出发，通常 5 到 6 步就逼近 sqrt(x) 了，比二分的 31 步明显少。

但题目要的是整数答案，所以不能直接套浮点牛顿，不然会卡在精度判断上。整数版本的真实做法是：在每一步都用整型运算算出下一个猜测guess = (guess + x / guess) / 2，然后只要guess * guess > x就继续迭代，否则返回 guess。

为什么这个停止条件是可靠的？因为序列只会从大于等于 sqrt(x) 的一侧往下走。初始 guess = x 一定大于等于 sqrt(x)；只要不为满足条件而直接返回，序列就会继续收缩。当 guess 落到 floor(sqrt(x)) 时，下一步会算出同样的值或者卡在相邻值，此时guess * guess <= x首次成立，说明我们已经到达了最后一个“平方不超过 x”的整数。由于题目要求向下取整，这个 guess 就是答案。

有个边界要注意：x = 0 和 x = 1 时，直接返回 x。原因很简单，初始 guess = x，guess * guess > x在 x=0 时是0 > 0，直接退出，勉强也行；但 x=1 时1 > 1也是退出，结果也对。真正危险的是某些扩展版本里初始 guess 是 0，就会出现除零。所以我习惯在开头把 0 和 1 一起特判掉，少一个心腹大患。

3.3 完整实现与一个精度陷阱

C++ 完整代码如下：

class Solution { public: int mySqrt(int x) { if (x < 2) return x; long long guess = x; while (guess * guess > x) { guess = (guess + x / guess) / 2; } return (int)guess; } };

这里我把 guess 声明成 long long，是为了让guess * guess在接近 int 上限时不溢出。换个角度，你也可以把判断写成guess > x / guess，这样连 long long 都能省掉，但为了代码可读性，我保留了乘法并用 long long 兜底。

Python 版长这样：

class Solution: def mySqrt(self, x: int) -> int: if x < 2: return x guess = x while guess * guess > x: guess = (guess + x // guess) // 2 return guess

一个容易翻车的地方是：有人觉得 float 版的牛顿收敛更快，于是先转成 double，算出 sqrt(x) 再强转 int。这个方法在 x 是完平方数时一般没事，但在 x 接近 INT_MAX 的某些边界值上，double 的 53 位精度不足以精确表示2^31 - 1这样的大整数，强转回来可能差 1。所以答案要的是精确整数，就别用浮点参与判断。这也是我在 LeetCode 上真见过的错误写法：本地测试通过，一到提交就挂。

4. 两种解法对比：面试聊什么、工程用什么

4.1 复杂度与迭代次数实测对比

二分法和牛顿法的时间复杂度都是对数级别，但常数不一样。我在自己机器上对 int 最大值做了个粗糙的实测（不计 I/O，只数循环次数）：二分大概进入 31 次左右循环，牛顿迭代大概在 6 次左右就停了。差距在单次调用里感觉不到，但如果把这道题改成一个批量场景——比如要对 100 万个整数分别求整数平方根，牛顿法的时间优势就会被放大。

用表格整理一下：

一个需要冷静看待的点：LeetCode 判题时这两种写法都是毫秒级通过，单次调用的性能差异对通过率影响为零。选择哪一种，更多是看你更熟悉哪条技术路线，以及面试官希望听到什么样的解释。

4.2 从这道题延伸出的工程启发

如果只把这题当作“背一个二分模板”，价值会缩水一半以上。它更大的意义是帮你建立类型意识：看到一个“求边界整数”的问题，先测试单调性；看到一个“求方程数值根”的问题，先想到切线迭代。这两条思维链条能直接迁移到旋转数组、二分答案、浮点数二分、以及很多数值计算场景。

在真正的工程代码里，你不太需要自己手写整数平方根——现代语言的标准库都会做，而且做了很多边界优化。但“在单调区间里二分找分界点”这种抽象能力，在搜索引擎的归并、存储系统的分页、推荐系统的阈值切分里会反复出现。牛顿迭代的思想则渗透在机器学习领域的梯度下降、拟牛顿方法里。所以把 69 题当成一个思想孵化器来刷，性价比很高。

5. 测试用例清单：把边界条件一次打满

5.1 边界四件套

刷题不能只在样例上跑。我把这题的必测输入固定成四个：0、1、2 和 2147483647。

为什么 2147483647 的答案是 46340 而不是 46341？因为 46340² = 2147395600，小于 INT_MAX；而 46341² = 2147488281，已经超出 INT_MAX。这个数值可以背下来，面试时直接口算。

5.2 平方数附近的组合测试

边界四件套之外，我会跑一组“平方数附近”的连续用例：对 n 从 1 到 10000，分别验证 n²、n²-1、n²+1 三个值。期望是：

• mySqrt(n*n)== n
• mySqrt(n*n - 1)== n - 1
• mySqrt(n*n + 1)== n

这一组用例能把答案附近的整数跳变全部测到。很多在边界上差 1 的 bug，靠这种规律性组合测试一测一个准。

5.3 通用验证断言函数

除了针对具体输入做期望断言，还可以写一个与答案无关的正确性校验函数。只要满足下面两条，结果就是合法的：

bool valid(int ans, int x) { return (long long)ans * ans <= x && (long long)(ans + 1) * (ans + 1) > x; }

这个函数用 long long 做乘法，避免 ans+1 接近 int 上限时溢出。然后用它对 0 到 100000 的随机数，或者干脆 0 到 1000000 全量跑一遍，两种解法交叉验证，任何一次返回不满足条件都会立刻暴露。

6. 我刷这道题踩过的三个坑

6.1 乘法溢出

第一个版本我用 C++ 写了mid * mid <= x。在 0 到普通测试用例上都对，提交到 x = 2147483647 就错。当时还纳闷，怎么代码逻辑这么顺还 WA。后来用调试器一看，mid 到 46341 时，mid*mid 在 int 里溢出成负数，判断直接反转。从那以后，我养成了习惯：涉及接近 int 上限的乘法，要么用 long long，要么改除法，顺手把验证用例也写进测试清单。

6.2 二分死循环

有段时间我习惯用l = mid这种模板写“找右边界”的题目。在 69 题里，一旦 l 和 r 相差 1，mid 取到 l，且 mid 可行，下一轮 l 还是原来的 mid，区间不收缩，程序直接超时。这个坑在面试白板题里尤其致命，因为你看不到运行结果，必须靠模板纪律兜底。现在我只记一条铁律：任何二分模板里，每一轮都必须让区间严格缩小。要么l = mid + 1，要么r = mid - 1；如果因为某种原因用了l = mid，那就要配套mid = (l + r + 1) / 2这种向右取整的写法。

6.3 面试追问：精确到小数点后几位怎么办

有一次一面，面试官在我给出二分写法之后追问：如果改成“求平方根，保留三位小数，不调库”，你怎么做？我的思路是回到连续二分：左边界 0，右边界 x，循环条件变成r - l > 1e-4，每次判断mid * mid与 x 的大小关系，循环结束后取 l 作为答案，再格式化。牛顿迭代也可以，但要把停止条件改成相邻两次结果差小于阈值。这个追问的意义不是真让你手写一个工业级sqrt，而是看你有没有从离散问题迁移到连续问题的能力。所以刷 69 题时，最好把这两种场景都过一遍。

这道题我刷了不止一遍。有段时间每次面试复习，我都会先把 69 题的二分版和牛顿版默写一遍，再用边界四件套跑一遍，整个过程不到十分钟，但手感和对溢出的警惕性一下就回来了。如果你的面试清单里正好有二分和数值计算相关的题目，强烈建议把这题当成热身项目，练到能闭眼默写为止。最后再分享一个小技巧：C++ 里判断边界时少用mid * mid，多用mid <= x / mid，这个习惯在别的二分题里也会帮你少踩好几次溢出。