AcWing 789/790 题解二分查找浮点数精度控制与整数边界处理的5个关键点在算法竞赛和日常编程中二分查找是最基础也最容易被低估的算法之一。表面上看它简单直接——不就是不断对半分割区间吗但当你真正在AcWing 789整数二分和790浮点数二分这样的题目上栽过跟头就会意识到二分查找的魔鬼全在细节里。为什么我的代码会陷入死循环为什么浮点数结果总是差那么一点点这些问题的答案往往隐藏在边界条件和精度控制的细微之处。1. 整数与浮点数二分的本质差异二分查找的核心思想是通过不断缩小搜索范围来快速定位目标但整数和浮点数二分在实现上有着根本性的区别。理解这些差异是写出正确代码的第一步。1.1 循环终止条件的对比整数二分的循环通常使用while(left right)或while(left right)而浮点数二分则采用while(right - left eps)的形式。这种差异源于它们的本质// 整数二分典型结构 while (left right) { int mid (left right) 1; if (check(mid)) right mid; else left mid 1; } // 浮点数二分典型结构 const double eps 1e-8; while (right - left eps) { double mid (left right) / 2; if (check(mid)) right mid; else left mid; }关键差异整数二分通过指针重合终止left right浮点数二分通过区间足够小终止区间长度 ≤ eps1.2 边界更新的不同策略在整数二分中我们通常需要谨慎处理mid的加减1以避免死循环。例如在寻找右边界时// 寻找右边界需要1 int mid (left right 1) 1; if (check(mid)) left mid; else right mid - 1;而浮点数二分则不需要这种考虑因为浮点数的除法天然会产生新的中间值// 浮点数二分无需考虑±1 double mid (left right) / 2; if (check(mid)) right mid; else left mid;1.3 结果确定性的区别整数二分的结果是精确的——要么找到确切值要么确定不存在。而浮点数二分得到的是一个近似解其精度取决于eps的取值特性整数二分浮点数二分结果类型精确值近似值终止条件指针位置区间大小边界更新需要±1直接赋值常见应用查找位置求方程解2. 整数二分的两种模板与边界陷阱整数二分最大的挑战在于正确处理边界条件避免死循环和漏判。根据问题需求我们通常使用两种模板。2.1 寻找左边界第一个满足条件的元素int left_bound(int q[], int len, int x) { int l 0, r len - 1; while (l r) { int mid (l r) 1; if (q[mid] x) r mid; else l mid 1; } return q[l] x ? l : -1; }关键点mid计算使用普通除法向下取整满足条件时移动右指针r mid不满足时左指针跳过midl mid 12.2 寻找右边界最后一个满足条件的元素int right_bound(int q[], int len, int x) { int l 0, r len - 1; while (l r) { int mid (l r 1) 1; if (q[mid] x) l mid; else r mid - 1; } return q[r] x ? r : -1; }关键差异mid计算需要1防止死循环满足条件时移动左指针l mid不满足时右指针跳过midr mid - 12.3 边界条件验证在AcWing 789题数的范围中我们需要同时找到元素的第一次和最后一次出现位置。这正好对应了两种模板// 解决AcWing 789的完整示例 void find_range(int q[], int len, int x) { // 找左边界 int l 0, r len - 1; while (l r) { int mid (l r) 1; if (q[mid] x) r mid; else l mid 1; } if (q[l] ! x) { cout -1 -1 endl; return; } cout l ; // 找右边界 r len - 1; while (l r) { int mid (l r 1) 1; if (q[mid] x) l mid; else r mid - 1; } cout r endl; }3. 浮点数二分的精度控制艺术浮点数二分看似简单但精度控制不当会导致结果错误或效率低下。以AcWing 790题数的三次方根为例我们需要特别关注几个关键点。3.1 精度值eps的选择eps决定了结果的精确程度通常取题目要求精度再缩小1-2个数量级。例如题目要求保留6位小数eps取1e-8const double eps 1e-8; double cube_root(double n) { double l -10000, r 10000; while (r - l eps) { double mid (l r) / 2; if (mid * mid * mid n) r mid; else l mid; } return l; }精度选择原则保留k位小数 → eps 1e-(k2)过小的eps会导致循环次数过多过大的eps会影响结果精度3.2 初始区间的确定浮点数二分需要合理设置初始搜索区间。对于三次方根问题我们注意到对于n∈[-10000,10000]其三次方根必然在[-100,100]之间保守设置初始区间为[-10000,10000]确保覆盖所有可能3.3 避免精度丢失的技巧在浮点数比较中直接使用往往不可靠。更稳健的做法是// 更稳健的浮点数比较 bool equal(double a, double b) { return fabs(a - b) eps; }在二分过程中即使条件看似简单也应考虑精度因素// 更安全的判断条件 if (mid * mid * mid - n eps) // 代替 mid*mid*mid n4. 从STL模板到竞赛题目的适配C标准库提供了lower_bound和upper_bound理解它们的实现原理有助于我们自定义二分逻辑。4.1 STL实现原理分析lower_bound返回第一个不小于目标值的位置其等效实现templateclass ForwardIt, class T ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T value) { ForwardIt it; typename std::iterator_traitsForwardIt::difference_type count, step; count std::distance(first, last); while (count 0) { it first; step count / 2; std::advance(it, step); if (*it value) { first it; count - step 1; } else { count step; } } return first; }4.2 适配AcWing题目的技巧将STL风格适配到AcWing 789题目void stl_style(int q[], int len, int x) { int l lower_bound(q, q len, x) - q; if (l len || q[l] ! x) { cout -1 -1 endl; return; } int r upper_bound(q, q len, x) - q - 1; cout l r endl; }4.3 自定义比较函数对于复杂数据结构可以自定义比较函数struct Node { int val; // 其他字段... }; bool cmp(const Node a, const Node b) { return a.val b.val; } int find_node(Node nodes[], int len, int target) { return lower_bound(nodes, nodes len, target, cmp) - nodes; }5. 调试与验证确保二分正确性的方法即使经验丰富的选手也会在二分查找上犯错因此建立系统的调试方法至关重要。5.1 常见错误模式分析死循环通常由于边界更新不当导致忘记在left mid时让mid (left right 1) 1浮点数二分误用整数二分的更新方式漏判元素终止条件设置不当使用while(left right)但漏判left right的情况浮点数eps设置过大导致提前终止结果偏移指针更新逻辑错误该加1时没加该直接赋值时却加了15.2 测试用例设计策略设计测试用例应覆盖以下场景测试类型示例输入预期输出空数组[]-1单元素匹配[5], 50 0单元素不匹配[3], 5-1全相同元素[2,2,2], 20 2无匹配元素[1,3,5], 4-1边界值[INT_MIN, INT_MAX], INT_MAX1 15.3 可视化调试技巧通过打印中间状态辅助调试void debug_binary_search(int q[], int len, int x) { int l 0, r len - 1; while (l r) { int mid (l r) 1; printf(l%d, r%d, mid%d, q[mid]%d\n, l, r, mid, q[mid]); if (q[mid] x) { cout Found at mid endl; return; } if (q[mid] x) l mid 1; else r mid - 1; } cout Not found endl; }对于浮点数二分可以记录迭代次数和精度变化void debug_float_search(double n) { double l -100, r 100; int iter 0; const double eps 1e-8; while (r - l eps) { double mid (l r) / 2; printf(Iter %d: [%.10f, %.10f], mid%.10f\n, iter, l, r, mid); if (mid * mid * mid n) r mid; else l mid; } printf(Final result: %.10f after %d iterations\n, l, iter); }掌握这些关键点后面对各种二分查找变种题目时你能够快速识别问题本质选择适当的模板并确保实现的正确性。记住二分查找的难点不在于算法思想本身而在于对各种边界条件的精确把控。