- 正确答案：使用二分查找法或牛顿迭代法求整数平方根，返回 floor(sqrt(x))。例如输入 8，输出 2；输入 16，输出 4。 - 解答思路：该题要求在不调用 sqrt() 等内置函数的前提下，对非负整数 x 求其平方根的整数部分（向下取整）。由于结果一定落在 [0, x] 区间内，且函数 f(k) = k² 在该区间单调递增，因此可采用二分查找——每次取中点 mid，比较 mid² 与 x 的大小关系：若 mid² == x，直接返回 mid；若 mid² < x，则答案在 [mid+1, r]；若 mid² > x，则答案在 [l, mid−1]。注意 mid² 可能溢出（尤其当 x 接近 INT_MAX 时），应使用 long long 或改写为 mid < x / mid（当 mid > 0）来避免溢出。牛顿迭代法亦可：求 f(t) = t² − x = 0 的非负根，迭代公式为 t_{n+1} = (t_n + x / t_n) / 2，初始值可设为 x（或 x//2+1），迭代至收敛（相邻两次差值小于 1e−6 或整数层面 |t_{n+1} − t_n| < 1），最后向下取整。但整数场景下牛顿法需注意整数除法截断问题，推荐用 long long 迭代并判断 t_{n+1} ≥ t_n 作为终止条件（因序列单调递减收敛）。 - 深度知识讲解：本题本质考察对**单调函数零点/下界搜索**的建模能力，以及对**整数边界与溢出控制**的工程敏感性。 ▶ 二分查找的底层逻辑依赖于**全序关系**和**单调性**：整数平方函数在 [0, ∞) 严格递增，故满足二分前提。注意：虽然数学上 sqrt(x) ∈ [0, x]，但更紧的上界是 min(x, 46341)，因为 46341² ≈ 2.147e9 < 2³¹−1，而 46342² > INT_MAX，这对 32 位 int 输入可进一步缩小搜索空间。 ▶ 溢出处理是关键考点：x 最大为 2³¹−1 ≈ 2.1e9，此时 mid 最大可达 ~46341，mid² 最大约 2.1e9 —— 恰好处于 int 边界。若用 int mid * mid，中间乘积会溢出（有符号溢出为未定义行为）。正确做法有三：(1) 强转为 long long 计算；(2) 改用除法比较：mid <= x / mid（仅当 mid > 0 时成立，需特判 mid==0）；(3) 使用无符号整数或 int64_t。 ▶ 时间复杂度：二分法为 O(log x)，牛顿法为 O(log log x)（二次收敛），但常数因子略高；空间复杂度均为 O(1)。 ▶ 稳定性与精度：二分法天然保证整数解精确性（不会因浮点误差导致 floor 错误），而牛顿法在整数迭代中若用整数除法（如 C++ 中 x/t_n 是截断除法），可能震荡或收敛慢，需额外校验。工业级实现（如 glibc 的 sqrt）通常结合位运算+牛顿法，但面试中二分法最稳妥、最易验证。 - 代码示例（C++ 风格，使用二分查找，安全防溢出）： ``` int mySqrt(int x) { if (x == 0) return 0; long long l = 1, r = x; while (l <= r) { long long mid = l + (r - l) / 2; long long sq = mid * mid; if (sq == x) { return (int)mid; } else if (sq < x) { l = mid + 1; } else { r = mid - 1; } } return (int)r; // 循环结束时 r 是最大满足 k*k <= x 的整数 } ``` 或使用除法避免 long long（更省内存，适用于嵌入式场景）： ``` int mySqrt(int x) { if (x == 0) return 0; int l = 1, r = x; while (l <= r) { int mid = l + (r - l) / 2; if (mid <= x / mid) { // 等价于 mid*mid <= x，且无溢出 if ((mid + 1) > x / (mid + 1)) return mid; // 下一个越界，mid 即答案 l = mid + 1; } else { r = mid - 1; } } return r; } ``` - 扩展知识： ▶ 进阶变体：求浮点数平方根（保留 n 位小数），可用二分（区间 [0,x] 细分）或牛顿法（收敛快）； ▶ 位运算解法（手工开方）：按二进制从高位到低位逐位确定结果，类似竖式开方，时间复杂度 O(log x)，空间 O(1)，适合硬件实现； ▶ 数学背景：该问题是整数平方根（Integer Square Root, isqrt）问题，在密码学（如 RSA 参数生成）、计算机图形学（距离比较）中频繁出现；Python 3.8+ 已内置 math.isqrt(x) 函数，其 CPython 实现即基于位运算优化的牛顿法； ▶ 面试陷阱提醒：勿用 for 循环暴力枚举（O(√x) 可能超时，x=2e9 时需循环 4.5e4 次，虽勉强通过但体现不了算法素养）；勿忽略 x=0 和 x=1 的边界；勿在比较中写成 mid * mid <= x 而不处理溢出。

小红书实习多模态大模型一面

全站热榜

创作者周榜