【算法精讲】二分查找核心模板与边界处理实战-尧图网络科技

1. 二分查找算法基础入门

二分查找是计算机科学中最基础也最实用的算法之一。我第一次接触这个算法是在大学的数据结构课上，当时觉得这个算法简直太神奇了——它能在O(log n)的时间复杂度内完成查找，比线性查找快得多。但真正开始刷题后才发现，看似简单的二分查找藏着不少"坑"。

二分查找的核心思想很简单：对于一个有序数组，每次通过比较中间元素和目标值的大小关系，将搜索范围缩小一半。这个过程就像我们小时候玩的"猜数字"游戏：对方心里想一个1-100的数字，你每次猜中间值，对方告诉你大了还是小了，这样最多7次就能猜中。

但实际应用中，二分查找的变体很多，比如：

查找精确值
查找左边界（第一个等于目标值的位置）
查找右边界（最后一个等于目标值的位置）
查找近似值（最接近目标值的位置）

这些变体虽然核心思想相同，但在边界条件处理上各有特点。很多初学者（包括当年的我）经常在这些细节上栽跟头，比如：

循环条件是left < right还是left <= right？
mid计算时要不要加1？
更新边界时是mid还是mid±1？

2. 整数二分查找的两种核心模板

经过大量练习和踩坑后，我总结出了两种最常用的整数二分模板，分别对应查找左边界和右边界的情况。这两种模板几乎可以解决所有整数二分问题。

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; // 结束时l==r }

这个模板的特点是：

循环条件是l < r，结束时l和r相等
mid计算不需要加1
当check(mid)为真时，r=mid；否则l=mid+1

实际应用示例（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; // 结束时l==r }

这个模板的不同之处在于：

mid计算需要加1，防止死循环
当check(mid)为真时，l=mid；否则r=mid-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 死循环问题

最典型的错误是查找右边界时忘记mid+1，导致死循环。比如：

// 错误示例：可能陷入死循环 int SR(int l, int r) { while (l < r) { int mid = l + r >> 1; // 忘记+1 if (q[mid] <= x) l = mid; // 当l=r-1时会卡住 else r = mid - 1; } return r; }

解决方法：当更新l=mid时，必须确保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, vector<int> &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; vector<int> v; for (int i = 0; i < n; i++) { cin >> tmp; v.push_back(tmp); } while (q--) { cin >> k; solve(k, v); } return 0; }