- 正确答案：实现 sqrt(x) 函数（返回非负整数 x 的平方根的整数部分，即 floor(sqrt(x))），要求不调用系统库函数，提供两种方法：（1）二分查找法：在区间 [0, x] 上搜索满足 k² ≤ x 的最大整数 k；（2）牛顿迭代法：求解方程 f(t) = t² − x = 0 的非负根，迭代公式为 t_{n+1} = (t_n + x / t_n) / 2，初始值取 t₀ = x（或更优的 t₀ = max(1, x/2)），迭代至收敛（相邻两次差值小于精度阈值，或整数截断稳定）。 - 解答思路： 1. 二分查找法：由于 sqrt(x) 单调递增，且对任意整数 k，k² 是单调不减的，因此可在整数域上做二分搜索。注意边界处理：x=0 或 x=1 时直接返回；mid 计算需防溢出（用 left + (right−left)/2），比较时用 mid ≤ x/mid 替代 mid*mid ≤ x 避免 long long 溢出（尤其当 x 接近 INT_MAX 时，mid*mid 可能溢出 int）。最终返回 right（因循环结束时 left > right，且 right 是最后一个满足 right² ≤ x 的整数）。 2. 牛顿迭代法：本质是求 f(t)=t²−x 的正根。导数 f′(t)=2t，故牛顿更新式为 t ← t − (t²−x)/(2t) = (t + x/t)/2。该迭代在 t₀ > 0 时全局收敛于 √x，且二次收敛（误差平方级衰减）。对整数截断需求，可迭代至 |t_{n+1} − t_n| < 1e−3，再向下取整；但更稳健的做法是迭代至相邻两次整数部分不再变化（即 (int)t_{n+1} == (int)t_n），或直接用整数版本——仅维护整数变量 t，并以 t > x/t 作为终止条件（避免浮点运算），此时 t 即为 floor(sqrt(x))（该整数牛顿法需额外证明单调递减与收敛性，见深度讲解）。 - 深度知识讲解：【二分查找底层原理】二分查找依赖“有序性”和“决策单调性”。此处决策函数 isGood(k) = (k*k <= x) 是前缀真后缀假的单调函数（即存在临界点 k₀，所有 k ≤ k₀ 满足，k > k₀ 不满足），故可用二分定位最右满足位置。时间复杂度 O(log x)，空间 O(1)。关键细节： - 溢出防护：x 最大为 2³¹−1 ≈ 2.1e9，其 sqrt 约 46340，但 mid 最大可达 x（初始 right=x），mid*mid 必溢出 int（max int≈2.1e9）。故比较必须写成 mid <= x / mid（整数除法，当 mid>0），注意 x/mid 向零取整，但因 mid≤x 且 x≥0，该式等价于 mid*mid≤x（数学上成立，整数除法下需验证：若 mid*mid≤x，则 x/mid ≥ mid；反之若 x/mid ≥ mid，则 x ≥ mid*mid，因 x/mid 是 floor(x/mid)，故 x ≥ mid * floor(x/mid) ≥ mid*mid）。严格安全写法是使用 long long 临时变量，但面试中更考察溢出意识，故推荐除法比较。【牛顿迭代法底层原理】牛顿法是求解非线性方程 f(t)=0 的迭代法，几何意义是用切线逼近根。收敛性依赖：f 连续可导、f′(t)≠0 在根邻域、初值足够近。对 f(t)=t²−x，f′(t)=2t，在 t>0 时非零，且对任意 t₀>0，序列 {tₙ} 单调递减并收敛于 √x（可证 tₙ ≥ √x 且 tₙ₊₁ ≤ tₙ）。收敛阶为 2：|tₙ₊₁ − √x| ≈ C·|tₙ − √x|²。整数牛顿法优化：定义整数迭代 tₙ₊₁ = (tₙ + x / tₙ) / 2（整数除法），初始 t₀ = x（或 x>>1）。该序列仍保持 tₙ ≥ floor(√x)，且严格递减直至稳定。终止条件为 tₙ₊₁ ≥ tₙ（因整数除法导致可能震荡，实际观察发现一旦 tₙ₊₁ ≥ tₙ，tₙ 即为答案）。数学上可证：若 t > √x，则 (t + x/t)/2 > √x，且该值 < t；整数版虽有舍入误差，但不会越过 floor(√x)。该方法时间复杂度 O(log log x)（双对数级，远快于二分），但常数稍大。【对比与工程考量】 - 精度：二分法天然整数解；牛顿法需注意浮点精度（如用 double 迭代，x=2147395600 时可能因舍入返回 46340.99999…，floor 后错为 46340 而非正确 46341），故整数牛顿法更鲁棒。 - 边界：x=0 时，二分法 left=0,right=0 直接返回；牛顿法需特判（t₀=0 会导致除零），故初值应设为 max(1,x)。 - 应用延伸：硬件 sqrt 指令多基于牛顿法变种（如 Goldschmidt 算法）；二分法用于嵌入式无浮点单元场景。 - 代码示例（C++ 风格，纯整数实现，无浮点、无溢出）： // 方法一：二分查找（整数域，防溢出） int mySqrt_binary(int x) { if (x <= 1) return x; int left = 1, right = x; while (left <= right) { int mid = left + (right - left) / 2; if (mid <= x / mid) { // 等价于 mid*mid <= x，避免溢出 left = mid + 1; } else { right = mid - 1; } } return right; // right 是最大的满足条件的整数 } // 方法二：整数牛顿迭代（无需浮点，收敛快） int mySqrt_newton(int x) { if (x <= 1) return x; long long t = x; // 用 long long 防中间计算溢出（t + x/t 最大为 x + 1） while (t > x / t) { // 终止条件：t <= x/t，即 t*t <= x t = (t + x / t) / 2; } return (int)t; } 注：牛顿法中 t 声明为 long long 是因 x/t 是整数除法，但 t + x/t 可能达 x+1（如 x=INT_MAX），而 int 可能溢出，故用 long long 安全。若坚持全 int，可改写为 t = t/2 + x/(2*t)，但需处理奇偶舍入，复杂度上升，故推荐 long long 中间量。 - 扩展知识： 1. 更高阶方法：Halley 法（三阶收敛），迭代式 t ← t*(t²+3x)/(3t²+x)，但除法开销大，实际少用。 2. 位运算法（Quake III Fast Inverse Square Root）：通过 magic number 0x5f3759df 和牛顿校正，专用于 1/sqrt(x)，体现位操作与数值分析结合。 3. 数学本质：sqrt(x) 是 x 的 1/2 次幂，可通过指数对数转换：exp(0.5*ln(x))，但依赖 ln/exp 实现，不满足“手撕”要求。 4. 测试要点：需覆盖 x=0,1,2,3,4,100,2147395599（INT_MAX 前的完全平方数 46340²），验证整数截断正确性。

字节日常实习二面-大模型算法

全站热榜

创作者周榜