- 正确答案：使用二分查找在区间 [0, x] 内搜索最大的整数 mid，使得 mid * mid <= x。返回该 mid 值（即 floor(sqrt(x))）。时间复杂度 O(log x)，空间复杂度 O(1)；对于大整数需注意乘法溢出，应使用 long 类型或无符号类型做中间计算。 - 解答思路：平方根函数 sqrt(x) 是单调递增函数，其整数下界（floor）满足：存在唯一整数 r ∈ [0, x]，使得 r² ≤ x 且 (r+1)² > x。因此可将问题建模为“在有序整数区间中查找满足条件的最右边界”，属于二分查找的「查找最右满足条件的位置」变种。初始化 left = 0，right = x（因为对任意 x ≥ 0，有 √x ≤ x）；每次取 mid = left + (right - left) / 2（避免整型溢出），计算 square = (long)mid * mid；若 square == x → 找到精确平方根，直接返回 mid；若 square < x → mid 可能是候选解，但可能存在更大的解，故令 left = mid + 1，并记录当前 mid 为潜在答案；若 square > x → mid 太大，必须缩小上界，令 right = mid - 1。循环结束时，left > right，最后一次满足 square <= x 的 mid 即为所求 floor(sqrt(x))，通常在收缩 left 时更新答案，或直接返回 right（因循环不变式保证 right 始终是满足条件的最大候选）。 - 深度知识讲解：本题本质考察对二分查找边界的数学建模能力与循环不变式的理解。关键点包括：（1）搜索空间定义：虽然 √x ≤ x/2 对 x ≥ 4 成立，但为通用性（含 x=0,1）仍取 [0,x]；更优上界可设为 x>>1 + 1（即 max(1, x//2 + 1)），但非必需。（2）溢出防护：当 x 接近 Integer.MAX_VALUE（约 2^31−1 ≈ 2.1e9）时，mid 最大可达 ~2.1e9，mid*mid 将远超 int 范围（约 4.6e18 > 2^31−1），导致整型溢出（Java 中 silent wraparound，C/C++ 未定义行为）。必须将乘法操作提升至 64 位（如 Java 的 long，C 的 long long）再比较。（3）循环终止与返回值选择：采用 while (left <= right) 模式，维护不变式：[0, left) 中所有值均满足条件（或未验证），(right, x] 中所有值均不满足；最终 right 是最后一个满足 mid² ≤ x 的索引。因此可安全返回 right。该模式比“记录 ans”更简洁且不易出错。（4）与标准二分的区别：不是查找是否存在某个值，而是查找满足不等式的最大整数——属于“二分答案”（binary search on answer）范式，广泛用于最大化/最小化可行性问题（如 LeetCode 875 爱吃香蕉的珂珂、410 分割数组的最大值）。（5）底层原理关联：该算法依赖实数域中平方函数的严格单调性（x≥0 时 f(x)=x² 单调递增），从而保证解空间有序，这是二分适用的前提。若函数非单调（如 x² 在 [-5,5] 上），则无法直接二分。 - 伪代码（Java 风格，带溢出防护）： ``` public int mySqrt(int x) { if (x == 0) return 0; long left = 1; long right = x; // 注意：x 是 int，但 right 用 long 避免后续计算溢出 while (left <= right) { long mid = left + (right - left) / 2; long square = mid * mid; if (square == x) { return (int) mid; } else if (square < x) { left = mid + 1; } else { right = mid - 1; } } return (int) right; // 循环结束时 right 是最大的满足 mid*mid <= x 的整数 } ``` - 扩展知识：（1）牛顿迭代法对比：可求浮点平方根，迭代公式 x_{n+1} = (x_n + a/x_n)/2，收敛速度快（二次收敛），但涉及浮点运算与除法，整数环境下需处理精度截断；而二分法纯整数运算，逻辑清晰，更适合面试手写。（2）位运算解法（如逐位确定法）：从最高位（如 1<<15）开始试探，若 (ans | bit)^2 <= x，则 ans |= bit，时间复杂度 O(log x)，常数更小，但思维难度高，非主流考察点。（3）实际系统实现：glibc 的 sqrt 使用硬件指令（如 x86 的 sqrtsd）或查表+牛顿法组合；Java Math.sqrt() 委托 JVM 内置优化实现，非简单二分。（4）相关变种题： • LeetCode 69：本题原题（返回整数部分）； • LeetCode 367：判断是否为完全平方数（可复用此逻辑，最后校验 ans*ans == x）； • LeetCode 702：在未知大小的有序数组中搜索（需先用指数探测确定右边界，再二分）。

小红书多模态交易算法二面55min

全站热榜

创作者周榜