1. 二分查找的边界艺术从基础到进阶二分查找是信息学竞赛中最经典的算法之一但很多选手在掌握了基础写法后遇到查找第一个大于等于x的元素这类变体问题时就会手足无措。这就像学会了骑自行车却不知道如何应对上坡路段一样。实际上二分查找的精髓就在于对边界的精确控制。我们先看一个简单例子在有序数组[1,3,5,7,9]中查找数字5。基础二分查找会这样操作初始化left0, right4第一次mid2找到数字5直接返回但当问题变成查找第一个大于等于4的元素时事情就变得微妙了。这时候我们需要考虑当mid元素等于目标值时如何处理当mid元素小于目标值时如何调整边界当mid元素大于目标值时如何保留可能解int lower_bound(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; }这个经典的lower_bound实现展示了二分查找边界控制的核心思想通过调整左右指针的移动策略我们可以精确控制查找的边界条件。在OpenJudge NOI 1.11的和为给定数题目中这种技巧尤为重要。2. 左闭右开 vs 左闭右闭区间选择的艺术二分查找有两种常见的区间表示方法左闭右开[left, right)和左闭右闭[left, right]。这两种写法看似相似实则暗藏玄机。左闭右开区间Python风格的特点是初始right数组长度循环条件为left rightright更新为mid时不减1// 左闭右开写法 int binary_search(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; else if (nums[mid] target) left mid 1; else right mid; } return -1; }左闭右闭区间传统风格的特点是初始right数组长度-1循环条件为left rightright更新为mid时需要减1// 左闭右闭写法 int binary_search(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; else if (nums[mid] target) left mid 1; else right mid - 1; } return -1; }在实际解题时我建议统一使用左闭右开写法因为与STL的lower_bound等函数保持一致处理空区间更方便right初始化为nums.size()即可边界条件更简单不容易出错在OpenJudge NOI 1.11的查找最接近的元素题目中区间选择直接影响着最终结果的正确性。我曾在这个问题上踩过坑当时因为混用两种写法导致边界条件处理错误调试了整整两个小时才找到问题所在。3. 四大经典变体问题解析掌握了基础二分查找后我们需要攻克四个经典变体问题。这些问题在信息学竞赛中频繁出现是区分选手水平的重要标尺。3.1 查找第一个等于x的元素这个问题要求找到目标值第一次出现的位置。关键在于当nums[mid] target时我们不能直接返回而要继续向左搜索。int first_equal(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid; } else { left mid 1; } } return (left nums.size() nums[left] target) ? left : -1; }3.2 查找最后一个等于x的元素与第一个等于x的问题对称我们需要找到目标值最后一次出现的位置。这时候需要在nums[mid] target时继续向右搜索。int last_equal(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid; } else { left mid 1; } } return (left 0 nums[left-1] target) ? left-1 : -1; }3.3 查找第一个大于等于x的元素这就是著名的lower_bound问题。在和为给定数这类题目中我们经常需要用它来快速定位。int lower_bound(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid; } else { left mid 1; } } return left; }3.4 查找最后一个小于等于x的元素这是upper_bound的变体在解决范围查询问题时非常有用。int upper_bound(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid; } else { left mid 1; } } return left - 1; }这四种变体的核心区别在于等于条件时的处理方式大于/小于条件时的边界调整最终返回值的校验建议在理解的基础上背下这四种模板并在实际题目中灵活应用。我在初学时就整理了一张对比表格帮助记忆这些细微差别。4. OpenJudge NOI 1.11实战解析让我们通过OpenJudge NOI 1.11的几个典型题目看看二分查找边界控制的实际应用。4.1 查找最接近的元素这是二分查找的入门题但隐藏着不少陷阱。题目要求在非降序列中找到与给定值最接近的元素如果有多个取较小的那个。解题思路先处理边界情况x小于最小值或大于最大值使用lower_bound找到第一个大于等于x的位置比较该位置和前一个位置与x的差值#include bits/stdc.h using namespace std; int main() { int n, m, x; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; cin m; while (m--) { cin x; if (x a[0]) { cout a[0] endl; continue; } if (x a.back()) { cout a.back() endl; continue; } int left 0, right n; while (left right) { int mid left (right - left) / 2; if (a[mid] x) left mid 1; else right mid; } if (abs(a[left-1] - x) abs(a[left] - x)) cout a[left-1] endl; else cout a[left] endl; } return 0; }这个解法巧妙利用了lower_bound的特性注意当所有元素都小于x时left会等于n但我们在前面已经处理了这种特殊情况。4.2 和为给定数这道题要求判断数列中是否存在两个数它们的和等于给定的数。高效的解法是先排序然后对每个元素a[i]用二分查找判断(target - a[i])是否存在。#include bits/stdc.h using namespace std; int main() { int n, target; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; cin target; sort(a.begin(), a.end()); for (int i 0; i n; i) { int complement target - a[i]; int left i 1, right n; while (left right) { int mid left (right - left) / 2; if (a[mid] complement) { cout a[i] complement endl; return 0; } else if (a[mid] complement) { left mid 1; } else { right mid; } } } cout No endl; return 0; }这个解法的时间复杂度是O(nlogn)关键在于排序预处理对每个元素在剩余部分二分查找补数查找范围从i1开始避免重复配对4.3 派问题这是典型的二分答案问题。我们需要找到最大的派体积使得可以分给足够多的人。#include bits/stdc.h using namespace std; const double PI acos(-1.0); const double EPS 1e-6; bool canDivide(const vectordouble volumes, int people, double size) { int count 0; for (double v : volumes) { count static_castint(v / size); if (count people) return true; } return false; } int main() { int n, f; cin n f; vectordouble volumes(n); for (int i 0; i n; i) { int r; cin r; volumes[i] PI * r * r; } double left 0.0, right *max_element(volumes.begin(), volumes.end()); while (right - left EPS) { double mid left (right - left) / 2; if (canDivide(volumes, f 1, mid)) { left mid; } else { right mid; } } printf(%.3f\n, left); return 0; }二分答案问题的通用解法框架确定答案的可能范围[left, right]编写判断函数canDivide检查当前中间值是否可行根据判断结果调整搜索范围当范围足够小时终止循环5. 常见错误与调试技巧在教授信息学奥赛培训的过程中我发现学生们在二分查找上常犯以下几类错误死循环问题通常是因为循环条件与边界更新不匹配。比如使用left right作为条件但更新时却写left mid而不是left mid 1。边界遗漏忘记处理目标值小于所有元素或大于所有元素的情况。在查找最接近的元素问题中这种错误尤为常见。整数溢出计算mid时使用(left right) / 2而不是left (right - left) / 2当left和right都很大时会导致溢出。调试二分查找的技巧打印每次循环的left、right和mid值使用小数据测试边界情况编写测试用例包括目标值小于所有元素目标值大于所有元素目标值等于某个元素目标值不存在但位于数组中间空数组情况一个实用的调试模板void debug_binary_search(vectorint nums, int target) { int left 0, right nums.size(); cout Initial: left left , right right endl; while (left right) { int mid left (right - left) / 2; cout Loop: left left , right right , mid mid , nums[mid] nums[mid] endl; if (nums[mid] target) { left mid 1; cout Move left to left endl; } else { right mid; cout Move right to right endl; } } cout Final: left left , right right endl; }6. 性能优化与进阶技巧当数据规模达到1e5甚至1e6时二分查找的常数优化就变得重要了。以下是一些进阶技巧使用位运算代替除法mid (left right) 1。这在一些老旧的编译器中可能有性能提升但现代编译器通常会自动优化。循环展开手动展开2-3次循环迭代减少循环控制开销。但会降低代码可读性建议只在性能瓶颈处使用。缓存友好访问如果比较操作涉及复杂计算可以考虑预计算并缓存结果。三分查找用于寻找单峰函数的极值点。每次迭代将区间分成三部分适用于某些特殊问题。// 三分查找示例寻找凸函数的极小值 double ternary_search(double left, double right) { while (right - left EPS) { double m1 left (right - left) / 3; double m2 right - (right - left) / 3; if (f(m1) f(m2)) { right m2; } else { left m1; } } return (left right) / 2; }二分答案与其他算法结合很多复杂问题可以转化为二分答案问题如最大值最小化问题最小值最大化问题可行性判断问题在信息学竞赛中二分查找的变体和应用远不止这些。真正掌握二分查找的边界艺术需要大量的练习和总结。建议从OpenJudge NOI 1.11的二分查找专题开始逐步攻克更复杂的问题。