1. 浮点二分的基础课为什么三次方根是个二分问题先说说我当年在 AcWing 算法基础课上做这道题时的真实感受。乍看标题AcWing 790. 数的三次方根第一反应是这有什么好讲的直接调用库函数不就行了——在 C 里用pow(n, 1.0/3.0)或者 Python 里用n ** (1/3)都能得到结果。但如果你真这么交上去虽然能过样例却错过了这道题真正想让你练的东西浮点数二分模板。AcWing 的题目编号 790 是浮点数二分的经典入门题它在算法基础课里的定位和整数二分的数的范围789是紧挨着的。两题放一起就是让你一次性把二分思想吃透搞清楚整数二分和浮点数二分到底差在哪里为什么浮点二分不需要考虑mid到底是取l还是l1。这是理解整个二分体系的关键一环跳过去的话后面遇到求方程近似解三分求极值这类变形题你会很容易绕晕。题目的描述其实很短给定一个浮点数n求它的三次方根结果保留 6 位小数。n的范围是浮点数负数的三次方根也是合法的比如 -8 的三次方根是 -2。所以这不是纯数学题也不是纯编程题而是用算法求方程的近似解的经典应用解x^3 n这个方程。为什么必须是二分因为 f(x) x^3 - n 这个函数是严格单调递增的。单调函数求零点二分是最朴素、最可靠、最好证明正确性的方法。你不需要导数的符号判断不需要迭代收敛性分析比如牛顿迭代只需要一个基本事实如果 f(mid) 和 f(l) 异号零点就在 [l, mid] 里否则就在 [mid, r] 里。这个逻辑比舍入误差更稳定比盲猜更可控。这道题也特别适合用来理解精度这个概念。你要保留 6 位小数那么二分的终止条件是什么不是l r而是r - l eps这个eps怎么取、取多少合适直接决定了你代码是对的还是错在边界上。我第一次做的时候就在这个问题上翻了车后面展开细说。适合什么人看这道题一是正在刷 AcWing 算法基础课、做到二分这一章的人二是学过数据结构、但一直没搞懂二分除了在有序数组里查找之外还能干嘛的人三是想系统整理浮点数二分边界细节、避免精度判题 WA 的人。这篇文章我会把从题意拆解到代码实现、再到踩坑复盘的全过程都写出来保证你跟着看一遍就能彻底把这 6 分题稳稳拿到手。2. 边界选择为什么区间的左右端点不能拍脑袋定很多新手拿到这道题第一步就卡住了三分之一的边界到底怎么定有人说l 0, r n有人说l -10000, r 10000还有人直接l -1e5, r 1e5。哪个对为什么先说最常见的坑l 0, r n这个写法在 n 是正数时没问题但 n 一旦小于 1比如 n 0.008你就犯了方向性错误。因为 0.008 的三次方根是 0.2它比 n 本身还要大。如果你把右边界定成r n 0.008那整个可行区间 [0, 0.008] 里压根不含答案 0.2二分无论如何都不可能收敛到正确值。这是我当年做这道题遇到的第一个大坑换了三个写法才真正弄明白问题不是出在二分逻辑而是出在边界上。那稳妥的方案是什么第一种也是最省脑子的方案直接取一个覆盖题目所有可能输入的大区间比如l -10000, r 10000。这个范围怎么来的因为题目中说 n 是浮点数虽然没有严格限制范围但在 AcWing 平台这类题目通常要求 n 在绝对值 10000 以内。三次方根在 [-22, 22] 左右边界留足余量即可。这种做法的好处是不管 n 是正、是负、是小绝对值还是大绝对值答案一定落在区间里。坏处是如果你把eps定得特别小比如 1e-8那区间长度是 20000你需要迭代大约log2(20000 / 1e-8)次大概是 51 次左右。这完全是可以接受的浮点二分不像整数二分有步数焦虑多几次迭代毫无压力。第二种稍微优雅一点l -abs(n) - 1, r abs(n) 1。这个做法是以 n 的绝对值包络答案。理由是这样的当 |n| 1 时n 的三次方根绝对值一定小于 |n|当 |n| 1 时n 的三次方根绝对值反而大于 |n|。所以你直接取[-max(1, |n|), max(1, |n|)]其实是更严谨的写法。但大多数人图省事直接取[-1e5, 1e5]也不会错只是看起来不够讲究。第三种根据符号动态调整。我后来在实际工程里比较喜欢这样写double n; scanf(%lf, n); double l -1e5, r 1e5;然后在二分里判断mid * mid * mid n来决定往左还是往右。这个写法不需要讨论正负号因为三次方根函数在整个实数域上是单调递增的判断条件天然统一。所以边界选择的结论就是如果你不想动脑子就把边界设成 ±1e5如果你想让代码显得有理论依据就用l min(-1.0, n) - 1, r max(1.0, n) 1这类写法。但无论如何不要写l 0, r n然后祈祷 n 是大于 1 的正数。算法竞赛里没有什么比边界之外藏着答案更隐蔽的错误了。2.1 为什么负数不需要单独讨论浮点数二分和整数二分一个很大的区别就是你不需要对负数做特判。整数二分里mid (l r) / 2在负数区间上会有取整方向的问题所以你得区分l r 1是下取整然后对应l mid 1或者r mid - 1。但浮点二分里mid就是精确的中间值不存在取整方向问题判断条件也统一是正负号自带方向。具体到这道题你要找的是 x 使得x^3 n。如果 n -8那 x -2。你把区间设成 [-10000, 10000]mid 从 0 附近开始收敛通过mid * mid * mid和n的比较自然会把区间压到负数那一边。没有特殊分支没有绝对值转换代码量直接减半。这一点恰恰是这道题想教的浮点数的连续性让二分变得异常干净你只需要关心往左还是往右完全不用关心边界1还是-1。很多人在整数二分里反复背模板、背mid取值的口诀到浮点二分这里反而懵了其实是因为没意识到浮点二分才是二分的本质——连续空间上的单调逼近整数二分只是因为离散取整才引入了一堆麻烦。2.2 边界取 ±1e5 的合理性验证如果题目数据范围没有明说你怎么知道你设置的边界一定安全有个简单的验证方法在二分结束后打印l和r看看它们是否落在边界内部很远的地方。如果答案靠近边界说明你的边界有问题需要扩大。实际上 n 的三次方根增长非常缓慢n 1e9 时根才 1000n 1e12 时根才 10000。所以对绝大多数浮点数输入±1e5 完全是碾压级别的安全。哪怕遇到 n 1e15根也就 21544 左右依然安全。除非 n 是 1e18 量级但那已经不属于这类基础题的考察范围了。那为什么不直接把边界设成 ±1e18 一劳永逸因为浮点数在极大边界下做二分mid * mid * mid可能会发生溢出或精度下降。虽然double能表示 1e308 那么大但三次方乘法的中间积一旦超过 1e154精度就开始恶化。所以边界宁可行程大也不要大到失去精度。±1e5 是个记忆负担小、理论无懈可击的选择我个人的建议是直接照抄这个值不要自己发挥改成 ±1e4 或者 ±1e9。3. 精度控制的核心eps 到底取多少才不会 WA这是浮点数二分里最值得掰扯清楚的细节。题目要求保留 6 位小数那你的二分终止条件r - l应该小于多少很多人第一反应是保留 6 位那 eps 取 1e-6 呗。这个想法在思路上没错但在实际判题中容易踩到边界错误需要解释清楚。3.1 为什么 1e-6 可能不够用假设你二分结束时区间长度是 1e-6也就是说答案在 [l, r] 里且 l 和 r 的差是 1e-6。这时候如果你输出 l经过四舍五入保留 6 位小数结果和真实答案的误差是多少最坏情况下答案在你区间的右端点 r而你输出了 l两者的差是 1e-6。保留 6 位小数时它对最后一位的影响是满格的——可能把 0.123456 输出成 0.123457也可能输出 0.123455。如果判题系统的误差容限是 1e-6你就有可能在临界数据上 WA。这有点像你拿一把最小刻度是 1 毫米的尺子去量一根 1.0004 厘米的线读数没有太大偏差但如果要你精确到 0.1 毫米必须在读数后再估一位。二分这里也一样你想要的输出精度是 6 位小数那你的计算精度就应该是 7 位甚至 8 位让计算精度严格高于输出精度才不会出现边界抖动。所以常规做法是eps 1e-8有些保守派甚至会取1e-10。1e-8 的意思就是把区间压缩到 0.00000001这比 6 位小数1e-6高两个数量级。此时输出 l 或 r 的任意一个保留 6 位都是一模一样的字符串判题绝对不会因为输出端点选择而扣你分。3.2 迭代次数和 eps 的关系盲目缩小 eps 也不是完全没代价。区间 [l, r] 的长度假设是 2e5就是 ±1e5eps 取 1e-8那理论上需要迭代的次数大约是多少每迭代一次区间折半区间长度从 2e5 降到 1e-8需要将 2e5 除以 2 共多少次小于等于 1e-8算一下2e5 约等于 2^181e-8 约等于 2^-27总共需要 18 27 45 次左右如果 eps 取 1e-10那就多迭代 7 次52 次左右。在实际运行时四五十次循环对计算机来说连开销都算不上所以把 eps 设得更小一些比如 1e-8 或 1e-10性能上完全不用担忧。这也是浮点二分比整数二分让人舒心的地方整数二分你担心死循环浮点二分你只需要担心精度够不够循环次数天然可控。这里我要分享一个我自己用得很顺手的经验代码里不要写死while (r - l 1e-8)而是先定义一个const double eps 1e-8;后面要调精度时只改一个值。如果你用 C 写还可以直接写while (r - l eps)。原因很简单浮点数的比较和 debug 时命名常量比魔法数字可读性好得多而且当你把这道题的模板迁移到别的浮点二分场景时比如求平方根、求对数近似值只需要调整 eps 一个量不会四处找散落的魔法数字。3.3 输出格式的细节l 还是 r以及 printf 的舍入模式二分结束时区间的左右端点都在误差范围内输出哪一个理论上都可以。但如果你真的在临界数据上测试可能会发现输出 l 和输出 r 在第 6 位上有 1 的偏差。因为浮点数在计算机里的表示不是十进制的二进制的舍入误差和十进制保留位数的舍入误差会在边界处打架。解决方式很简单用printf(%.6lf\n, l)输出左端点或者右端点并且保证 eps 足够小二者舍入后一致。我自己的习惯是输出左端点因为整个二分过程里l始终是可行解的下界语义上更稳妥。还有一个很多人忽略的点C 语言的 printf 浮点数舍入是四舍六入五成双银行家舍入还是四舍五入实际上在绝大多数主流平台和编译环境里printf 对二进制浮点数转十进制输出采用的是当前舍入模式通常是到最近偶数但因为你已经把 eps 压到了远小于输出精度的程度这个舍入模式差异基本不会影响结果。只有在你 eps 恰好压线 1e-6 时才可能出现 0.000000 和 0.000001 的分野。再次归结到核心建议eps 取输出精度的百分之一甚至千分之一是浮点二分最稳的打法。4. 二分的判断条件与单调性证明二分能不能用核心在于单调性。这道题和有序数组查找还不完全一样你面对的是一个连续函数 f(x) x^3它是不是单调递增的答案显然是但为了心里踏实还是要走一遍逻辑任意取 x1 x2那么 x1^3 x2^3这个结论对负数也成立。比如 -2 1(-2)^3 -8 1^3 1。所以整个实数轴上 x^3 严格单调递增。对任意给定的 n方程 x^3 n 有且仅有一个解。这意味着二分的判断条件mid 的三次方大于等于 n 就往左收永远是良定义的不存在多解歧义。于是核心循环体就三行while (r - l eps) { double mid (l r) / 2; if (mid * mid * mid n) r mid; else l mid; }这段代码的判断条件是mid * mid * mid n。为什么大于等于时往左收因为三次方根函数是单调递增的如果 mid 的三次方已经大于 n说明 mid 偏大真正解在 mid 左边所以把右边界拉到 mid。如果 mid 的三次方还小于 n说明 mid 偏小真正解在 mid 右边所以把左边界拉到 mid。整个过程就是不停地把藏着答案的区间缩小。这里我想强调一个容易思维混乱的地方有些同学会把判断条件和线性查找类比写成 如果 n 大于 mid 的三次方就l mid但代码里却是if (mid * mid * mid n)。其实等价的只是方向问题。我的建议是每次写二分都先写清楚当前 mid 是偏大还是偏小偏大往哪收这个思维链条不要背模板。模板是给人用的但考场上一紧张模板会忘思维链不会。还有一个性能细节为什么这里用mid * mid * mid而不是pow(mid, 3)一是pow走的是通用幂运算内部可能调用 exp/log 组合性能比三次乘法慢一个量级在这种循环四五十次的场景里差别不大但在更复杂的浮点二分里会有明显差距二是pow在负数底数、小数指数时可能出现定义域问题或复数分支虽然指数是整数 3 可以绕开但乘法在语义上绝对安全。你在 AcWing 上提交代码后会看到实际耗时通常都是个位数毫秒但这不代表你可以随意挥霍性能——尤其后面学到三分、牛顿迭代、自适应辛普森性能习惯从现在就养起。5. 从 AcWing 790 到通用浮点二分模板的抽象说实话AcWing 790 这道题的代码量非常小核心部分可能就十行。但它的价值在于让你把浮点二分的骨架抽出来作为一种解决单调连续函数求零点的通用方法。现在我每次遇到给定 f(x)找 x 使得 f(x) target这类问题无论 f 是三次方根、指数函数、还是自定义的复杂函数都会直接套这个骨架// 通用浮点二分模板 const double eps 1e-8; double l -1e5, r 1e5; // 根据题目边界调整 while (r - l eps) { double mid (l r) / 2; if (f(mid) target) r mid; else l mid; } // 输出 l 或 r printf(%.6lf\n, l);唯一需要改的是f(mid)的具体实现和目标值 target。比如求平方根判断条件换成mid * mid n即可求x sin(x) c这种方程的近似解只要保证左式单调当然这里 x sin(x) 不是全局单调需要先找单调区间照样可以用同一套模板。所以我的建议是别把 790 当成一道即将被遗忘的签到题它是你浮点二分模板库的起点。把这个模板默写下来比背任何奇技淫巧都划算。5.1 浮点二分和整数二分的模板对照表这里我放一张对照表让两种二分各自的特征更清晰维度整数二分浮点二分mid 计算mid l r 1有取整方向mid (l r) / 2精确边界更新l mid 1 / r mid - 1跳过 midl mid / r mid区间包含 mid终止条件l r 或 l rr - l eps死循环风险存在需模板配合几乎不存在只有精度顾虑适用场景离散序列查找、边界定位连续函数求零点、方程近似解典型复杂度O(log n) 次比较O(log((R-L)/eps)) 次迭代从表里能看出来浮点二分的模板通用性更强心智负担更低。而整数二分的两个模板l mid 1配合mid l r 1 1以及r mid配合mid l r 1就是为了应对离散性和死循环风险才演化出来的。学完这道浮点二分再回头看整数二分你会更容易理解那些别扭的规则到底在防什么事。5.2 073 变体如果题目要求负数的三次方根怎么办有的同学可能在别的 OJ 上看到这道题的变体版本输入可能包含负数问你输出它的三次方根。其实 AcWing 790 本身就包含负数输入网上有一些题解额外写if (n 0) return -cbrt(-n)这种分支实际上是完全多余的。直接在 [-1e5, 1e5] 区间上做二分就能正确处理负数因为三次方根函数是整个实数域单调的。这个多余分支反映了作者对浮点二分单调性的理解还不到位你不用学它。但如果你真遇到了一个规定数值范围为负的极端场景比如 n -1e12那二分一样处理mid 在负数域内不断调整最终收敛到约 -10000整个过程中mid * mid * mid一直也是负数和 n 的比较逻辑依然正确。这是浮点数二分的漂亮之处——它不关心你的数值是正是负只关心单调方向。6. 实测代码与运行效果光说不练假把式我贴一份我实际提交过的 C 完整代码再贴一份 Python 版本给你做个双语言参考。C 版本#include cstdio int main() { double n; scanf(%lf, n); double l -1e5, r 1e5; const double eps 1e-8; while (r - l eps) { double mid (l r) / 2; if (mid * mid * mid n) r mid; else l mid; } printf(%.6lf\n, l); return 0; }Python 版本n float(input()) l, r -1e5, 1e5 eps 1e-8 while r - l eps: mid (l r) / 2 if mid ** 3 n: r mid else: l mid print(f{l:.6f})两个版本逻辑完全一致。C 跑 AcWing 平台快Python 日常验证思路方便你随便选一个学透都行。6.1 几组手算验证数据我拿几个容易出错的 n 值把二分跑的中间过程手算一下方便你对答案n 27预期输出 3.000000。区间初始 [-1e5, 1e5]mid 00^3 0 27l 跳到 0mid 50000显然大于 27r 跳到 50000……不断折半后收敛到 3.000000。这个例子看似简单但验证了算法在正数上的基本表现。n -8预期输出 -2.000000。注意 mid 在负数区域时mid * mid * mid也是负数和 n 比较时大小关系正确。比如 mid -1e5 时mid^3 -1e15 -8说明当前 mid 偏小-100000 比 -2 小得多所以 l 跳到 -1e5 不对是 l mid看判断条件-1e15 -8条件为假走 else所以 l mid -1e5——等等这里需要仔细走一遍mid 0 时0^3 0 -8成立r 0mid -50000 时(-50000)^3 -1.25e14 -8显然不成立负数比较大小-1.25e14 远远小于 -8所以 l -50000。这样区间不断往 0 附近收最终收敛到 -2。整个过程中 l 始终小于真实解r 始终大于真实解符合二分的闭环性质。n 0.008预期输出 0.200000。这个数据如果 l 0, r n 就会 WA但用 ±1e5 的边界毫无压力。收敛后区间在 0.2 附近输出 0.200000。n 0预期输出 0.000000。mid 0 时 mid^3 0 0r 0此后 l 不断往 0 靠输出 0没毛病。6.2 实测中常见的坑midmidmid 溢出与精度有些人用 float 而不是 double在 n 比较大时mid * mid * mid会先算成 float精度丢失严重导致二分收敛不稳定。解法很简单全部用 double不要混用。如果你的编译器把mid声明成 double那mid * mid * mid自动是 double 运算没有风险。但如果你写成float mid哪怕 r 和 l 是 double中间运算也会退化成 float精度直接掉一个量级。我见过有人用 float 交这道题 WA 了三次找不到原因最后就是把类型改成了 double 就好了。另一个隐藏坑是有的 OJ 开了-O2优化后浮点运算的中间精度可能在不同架构上有细微差异但 AcWing 的评测环境很标准不需要担心这个。你只需要保证自己的逻辑是对的然后用 double 运算这 6 分就是手拿把攥的。7. 我的常见错误总结三份 WA 代码的复盘7.1 错误一把右边界直接设成 n这是我在网上解答时看到的最频繁的错误代码形式double l 0, r n;只要 n 是大于 1 的正数这段代码确实能过。但它隐藏着两个隐患一是 n 小于 1 时直接 WA二是 n 为负数时 l 0, r n 导致区间为空。有些同学说自己运气好过了那是只测了 n 8 之类的用例一旦在 OJ 上遇到 n 0.001 的测试点就直接挂掉。所以边界设计不是能跑就行而是要在所有合法输入下都正确。我后来做了一道数据范围更大的浮点二分题深刻体会到边界写不对改起来比写新题还痛苦。7.2 错误二终止条件写成r - l 1e-6这个错误在思路上更隐蔽你觉得自己取 1e-6 和输出精度 1e-6 刚好对齐很合理但实际上属于极限操作。前面我们已经算过最坏情况下输出误差是满 1e-6会导致结果在第 6 位小数上摇摆。把 eps 改成 1e-8 后这个问题直接消失。我的经验是浮点二分的 eps 永远要比输出精度小两个数量级这是看起来浪费但永远正确的策略。7.3 错误三判断条件写成mid * mid * mid n且对应地l mid这个写法其实在数学上也是对的因为函数单调递增但方向反着写容易和r mid搞混。我不建议你反向写的原因是当你的目标函数不是严格单调、而只是单调不降时反向判断容易漏掉相等边界。对于三次方根这种严格单调的情形两种方向都行但为了养成好习惯我一直保留大于等于则收右边界的写法这样在复杂函数里也更安全。8. 延伸很多算法题背后都是浮点二分的变形最后说点这道题以外的东西。浮点二分在竞赛和面试题里出场率其实不低只是很多题目穿上了别的外衣。比如求一个数的平方根可以二分求两个有序数组的第 k 小距离对的距离可以二分答案给定一个函数求它和某个常数的交点可以二分。这种二分答案的思路和二分查找完全不同它是把最优解问题转化成判定可行性问题给你一个候选答案 mid问你它能不能满足条件。如果满足答案继续往更好的方向收不满足就换方向。AcWing 790 就是最简单的二分答案模型候选答案 mid 是三次方根可行性判定是mid^3 是否大于 n。一旦你掌握了这个模型后面遇到让最大值最小或让最小值最大的题比如经典的二分答案题 POJ 3258 River Hopscotch、AcWing 里 249 题奶牛排队就会觉得很眼熟。我个人在刷完这题之后又把同一个模板应用到了计算自然对数近似值、牛顿法和二分法对比测试这些场景里每次用都有新的体会——递归、二分、迭代三种逼近思想浮点二分是最好上手、最不容易出错的入门方式。如果你正在学算法基础课建议你拿这道题做一次深度笔记把它和后面的题目横向对比收获会比单纯 AC 一道题大得多。