1. 二分算法在竞赛中的核心地位二分查找这个看似简单的算法在算法竞赛中占据着举足轻重的位置。我参加过的所有编程比赛中几乎每三题就有一道需要用到二分思想。不同于教科书上基础的数组查找应用竞赛中的二分往往需要选手对算法进行创造性改造。去年一场区域赛中有一道关于网络延迟的题目表面看是图论问题但最优解法却是对延迟时间进行二分判定。这种跳出固定思维模式的应用正是二分算法在竞赛中的魅力所在。许多看似复杂的最大值最小化问题通过二分都能转化为简单的判定性问题。2. 二分查找的三种标准实现2.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; if (nums[mid] target) left mid 1; else right mid - 1; } return -1; }关键细节使用left right而不是left right可以确保所有元素都被检查到。计算mid时采用left (right - left)/2的写法可以避免整数溢出。2.2 lower_bound的实现原理STL中的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) left mid 1; else right mid; } return left; }这个实现有几个精妙之处初始右边界设为nums.size()而非nums.size()-1这样可以处理目标值大于所有元素的情况循环条件改为left right确保退出时left和right重合找到目标时不立即返回而是继续向左搜索2.3 upper_bound的竞赛应用upper_bound返回第一个大于目标值的位置常用于统计元素出现次数int count upper_bound(nums.begin(), nums.end(), target) - lower_bound(nums.begin(), nums.end(), target);在解决网线主管这类问题时upper_bound可以帮助我们快速确定满足条件的边界点。实际比赛中我经常将这两个函数组合使用来处理各种区间统计问题。3. 二分算法的五大经典变种3.1 旋转数组中的搜索这类问题在近年比赛中频繁出现。例如给定一个旋转后的有序数组[4,5,6,7,0,1,2]要求查找目标值的位置。解决思路是int 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; if (nums[left] nums[mid]) { // 左半部分有序 if (nums[left] target target nums[mid]) right mid - 1; else left mid 1; } else { // 右半部分有序 if (nums[mid] target target nums[right]) left mid 1; else right mid - 1; } } return -1; }3.2 峰值查找问题要求找出数组中任意一个峰值元素大于相邻元素。这个问题看似需要遍历实则可以用二分高效解决int findPeakElement(vectorint nums) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[mid 1]) left mid 1; else right mid; } return left; }这个解法利用了峰值必然存在于上升或下降趋势中的特性每次都能将搜索范围减半。3.3 无限序列中的查找当数据规模未知时比如流数据传统的二分无法直接应用。这时可以采用指数级扩张二分的方法int searchInfiniteArray(vectorint nums, int target) { int left 0, right 1; while (nums[right] target) { left right; right * 2; } return binary_search(nums, left, right, target); }3.4 带权二分优化带权二分又称二分答案是竞赛中的高级技巧常用于解决最优化问题。基本思路是将原问题转化为判定性问题确定答案的可能范围对中间值进行可行性判断根据判断结果缩小范围例如在网线主管问题中我们需要找到最长的网线长度使得能切割出至少K段。解法如下double max_length(vectordouble cables, int K) { double left 0, right *max_element(cables.begin(), cables.end()); for (int i 0; i 100; i) { // 固定迭代次数保证精度 double mid (left right) / 2; int count 0; for (double cable : cables) count (int)(cable / mid); if (count K) left mid; else right mid; } return left; }3.5 二维矩阵中的二分查找在行列都有序的矩阵中查找目标值可以将二维问题转化为一维bool searchMatrix(vectorvectorint matrix, int target) { if (matrix.empty()) return false; int m matrix.size(), n matrix[0].size(); int left 0, right m * n - 1; while (left right) { int mid left (right - left) / 2; int val matrix[mid / n][mid % n]; if (val target) return true; if (val target) left mid 1; else right mid - 1; } return false; }4. 二分算法的竞赛实战技巧4.1 循环不变式的维护写出正确的二分代码关键在于维护循环不变式。我总结的经验是明确搜索区间含义开闭区间确保每次迭代都朝着解的方向前进终止条件要能覆盖所有情况例如在lower_bound实现中我们维护的不变式是答案始终在[left, right]区间内且left之前的元素都小于目标right之后的元素都不小于目标。4.2 避免整数溢出计算mid时常见的(left right)/2写法在left和right都很大时会导致溢出。安全写法是int mid left (right - left) / 2;对于带符号整数也可以使用无符号右移int mid (left right) 1; // Java风格4.3 浮点数精度的处理在带权二分等涉及浮点数的问题中不能简单地使用相等判断。我通常采用两种方法固定迭代次数如100次设置误差容忍度while (right - left 1e-6) { // 二分过程 }4.4 调试技巧二分算法容易陷入死循环或返回错误结果。我的调试方法包括打印每次迭代的left、right和mid值检查循环不变式是否被破坏使用小规模测试用例验证边界条件5. 常见问题与解决方案5.1 死循环问题当left和right相邻时如果mid总是等于left可能会导致无限循环。解决方法确保mid计算能向右取整更新边界时至少移动一个位置5.2 边界条件错误常见错误包括初始范围设置不当返回值选择错误空输入处理缺失实战建议总是先考虑输入为空、单元素、双元素等边界情况。5.3 判定函数设计在带权二分中判定函数的设计至关重要。经验法则判定条件要严格单调处理边界情况要谨慎避免在判定函数中进行复杂计算6. 竞赛中的二分模板总结经过多年比赛积累我整理了一套通用的二分模板// 标准二分查找 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; if (nums[mid] target) left mid 1; else right mid - 1; } return -1; } // lower_bound风格 int find_first(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; } // upper_bound风格 int find_last(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; } // 带权二分框架 double binary_search_answer(double left, double right) { for (int i 0; i 100; i) { double mid (left right) / 2; if (check(mid)) left mid; else right mid; } return left; }在实际比赛中我会根据题目特点选择合适的模板进行改造。记住二分算法的核心思想是每次排除一半的搜索空间只要把握住这一点就能灵活应对各种变种问题。