前言
二分查找是算法竞赛中的高频考点，核心在于利用数据的二段性将复杂度从 O(n) 降至 O(log n)。下面通过两道经典例题，梳理从排序预处理到边界细节处理的完整流程。
一、A-B 数对
题目描述
给定一个整数序列和一个常数 C，求满足 A - B = C 的数对数量。
思路解析
方程可变形为 B = A - C。既然顺序不影响结果，先对数组排序。枚举每个 A，在已排序数组中二分查找等于 A - C 的元素个数。
这里涉及两个关键概念：
- lower_bound：返回第一个大于等于目标值的位置。
- upper_bound：返回第一个大于目标值的位置。 两者相减即为区间长度（即该数值出现的次数）。
注意，STL 函数仅适用于有序序列。如果数组无序，需先排序或利用'二段性'手动实现二分。
代码实现
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL a[N];
int main() {
int n, c;
cin >> n >> c;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
LL ret = 0;
for (int i = 2; i <= n; i++) {
LL b = a[i] - c;
// 在 [1, i] 范围内查找值为 b 的元素个数
ret += upper_bound(a + 1, a + i + 1, b) - lower_bound(a + 1, a + 1 + i, b);
}
cout << ret << endl;
;
}
