【算法精讲】二分查找 核心模板与边界处理实战

1. 二分查找算法基础入门二分查找是计算机科学中最基础也最实用的算法之一。我第一次接触这个算法是在大学的数据结构课上当时觉得这个算法简直太神奇了——它能在O(log n)的时间复杂度内完成查找比线性查找快得多。但真正开始刷题后才发现看似简单的二分查找藏着不少坑。二分查找的核心思想很简单对于一个有序数组每次通过比较中间元素和目标值的大小关系将搜索范围缩小一半。这个过程就像我们小时候玩的猜数字游戏对方心里想一个1-100的数字你每次猜中间值对方告诉你大了还是小了这样最多7次就能猜中。但实际应用中二分查找的变体很多比如查找精确值查找左边界第一个等于目标值的位置查找右边界最后一个等于目标值的位置查找近似值最接近目标值的位置这些变体虽然核心思想相同但在边界条件处理上各有特点。很多初学者包括当年的我经常在这些细节上栽跟头比如循环条件是left right还是left rightmid计算时要不要加1更新边界时是mid还是mid±12. 整数二分查找的两种核心模板经过大量练习和踩坑后我总结出了两种最常用的整数二分模板分别对应查找左边界和右边界的情况。这两种模板几乎可以解决所有整数二分问题。2.1 查找左边界的模板// 查找左边界返回第一个target的元素位置 int searchLeft(int l, int r) { while (l r) { int mid l (r - l) / 2; // 防止溢出 if (check(mid)) { // 通常为nums[mid] target r mid; } else { l mid 1; } } return l; // 结束时lr }这个模板的特点是循环条件是l r结束时l和r相等mid计算不需要加1当check(mid)为真时rmid否则lmid1实际应用示例AcWing 789. 数的范围int SL(int l, int r, int x) { while (l r) { int mid l r 1; if (q[mid] x) r mid; else l mid 1; } return l; }2.2 查找右边界的模板// 查找右边界返回最后一个target的元素位置 int searchRight(int l, int r) { while (l r) { int mid l (r - l 1) / 2; // 注意这里要1 if (check(mid)) { // 通常为nums[mid] target l mid; } else { r mid - 1; } } return r; // 结束时lr }这个模板的不同之处在于mid计算需要加1防止死循环当check(mid)为真时lmid否则rmid-1实际应用示例AcWing 789. 数的范围int SR(int l, int r, int x) { while (l r) { int mid l r 1 1; if (q[mid] x) l mid; else r mid - 1; } return r; }2.3 两种模板的选择技巧如何快速判断该用哪个模板我的经验是先明确要找的是左边界还是右边界画图分析check(mid)为真时应该更新哪个边界根据边界更新方式决定mid是否要1举个例子在AcWing 789中找左边界时我们希望尽可能向左移动所以当q[mid]x时更新右边界找右边界时我们希望尽可能向右移动所以当q[mid]x时更新左边界3. 边界条件与常见错误分析二分查找的难点不在于算法本身而在于各种边界条件的处理。下面是我总结的几个常见错误和解决方法3.1 死循环问题最典型的错误是查找右边界时忘记mid1导致死循环。比如// 错误示例可能陷入死循环 int SR(int l, int r) { while (l r) { int mid l r 1; // 忘记1 if (q[mid] x) l mid; // 当lr-1时会卡住 else r mid - 1; } return r; }解决方法当更新lmid时必须确保mid计算时有1。3.2 越界问题另一个常见错误是初始边界设置不当导致越界。比如数组长度为0时r初始为-1或者查找不存在的元素时返回了非法索引。解决方法检查输入数组是否为空检查返回值是否在合法范围内添加边界条件判断3.3 精度问题浮点数二分虽然这部分主要讨论整数二分但浮点数二分也有类似问题。常见错误是精度设置不当导致循环无法终止或结果不精确。解决方法根据题目要求设置合适的精度eps固定循环次数如循环100次也是一种可行方案4. 实战应用与题目解析4.1 AcWing 789. 数的范围这道题完美展示了二分查找左右边界的应用。解题步骤使用searchLeft找到第一个x的位置检查该位置是否确实等于x如果等于x再用searchRight找到最后一个x的位置输出两个位置完整代码#include iostream using namespace std; const int N 1e5 10; int q[N]; int SL(int l, int r, int x) { while (l r) { int mid l r 1; if (q[mid] x) r mid; else l mid 1; } return l; } int SR(int l, int r, int x) { while (l r) { int mid l r 1 1; if (q[mid] x) l mid; else r mid - 1; } return r; } int main() { int n, m; scanf(%d%d, n, m); for (int i 0; i n; i) scanf(%d, q[i]); while (m--) { int x; scanf(%d, x); int l SL(0, n - 1, x); if (q[l] ! x) cout -1 -1 endl; else { cout l ; cout SR(0, n - 1, x) endl; } } return 0; }4.2 AcWing 790. 数的三次方根这道题展示了浮点数二分的应用。注意点精度控制题目要求保留6位小数eps一般设为1e-8边界设置注意x可能为负数的情况代码示例#include iostream using namespace std; double n; int main() { cin n; double l -10000, r 10000; while (r - l 1e-8) { double mid (l r) / 2; if (mid * mid * mid n) r mid; else l mid; } printf(%.6lf\n, l); return 0; }5. STL中的二分查找函数C标准库提供了几个二分查找相关函数了解它们可以帮助我们快速解决一些问题lower_bound返回第一个target的元素位置upper_bound返回第一个target的元素位置binary_search判断元素是否存在使用示例AcWing 789的STL版本#include bits/stdc.h using namespace std; void solve(int k, vectorint v) { int l lower_bound(v.begin(), v.end(), k) - v.begin(); int r upper_bound(v.begin(), v.end(), k) - v.begin(); if (v[l] k) printf(%d , l); else printf(-1 ); if (v[r - 1] k) printf(%d\n, r - 1); else printf(-1\n); } int main() { int n, q, k, tmp; cin n q; vectorint v; for (int i 0; i n; i) { cin tmp; v.push_back(tmp); } while (q--) { cin k; solve(k, v); } return 0; }6. 调试技巧与性能优化6.1 调试技巧打印中间值在循环中加入打印语句观察l, r, mid的变化小数据测试用小的测试用例手动模拟算法执行过程边界测试测试空数组、单元素数组等特殊情况6.2 性能优化使用位运算代替除法mid (l r) 1避免不必要的函数调用对于频繁调用的check函数可以考虑内联7. 常见问题与解决方案在实际刷题过程中我遇到过各种二分查找的问题。这里分享几个典型问题和解决方法如何判断该用哪个模板先明确要找的是左边界还是右边界画图分析check条件为什么我的代码陷入了死循环检查mid计算是否需要1检查边界更新是否正确如何处理重复元素找左边界用第一个target的模板找右边界用最后一个target的模板浮点数二分如何设置精度一般比题目要求多2位或者使用固定循环次数8. 进阶练习推荐为了巩固二分查找技能我推荐以下练习题LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置LeetCode 35. 搜索插入位置AcWing 1221. 四平方和AcWing 1227. 分巧克力AcWing 730. 机器人跳跃问题每道题都有其特点比如四平方和需要结合哈希表分巧克力需要考虑如何设计check函数机器人跳跃问题需要转化问题模型记住二分查找的核心在于二分的思想而不仅仅是代码模板。很多问题看似与查找无关但可以通过巧妙的建模转化为二分查找问题。这需要大量的练习和经验积累。