二分查找笔记
2026-07-23 12:59:46
发布于：新疆
二分查找笔记整理
一、基础二分查找：查找 x 是否存在
前提：数组有序
核心思路
左右边界不断缩小范围，每次取中间值比较：
中间值 < x → x 在右边，l = mid + 1
中间值 > x → x 在左边，r = mid - 1
中间值 == x → 找到，返回下标
模板代码
cpp
#include<bits/stdc++.h>
using namespace std;
int a[100010];
int n, x;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> x;
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] < x) {
l = mid + 1;
} else if (a[mid] > x) {
r = mid - 1;
} else {
cout << mid;
return 0;
}
}
cout << -1; // 没找到
return 0;
}
二、lower_bound：第一个 >= x 的位置
手写版
思路： 满足条件时记录答案，继续往左找更优解
cpp
int l = 1, r = n;
int ans = n + 1; // 找不到默认 n+1
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] >= x) {
ans = mid; // 记录可能的答案
r = mid - 1; // 继续往左找第一个
} else {
l = mid + 1; // 太小，往右找
}
}
cout << ans;
STL 版
cpp
// 返回第一个 >= x 的地址，减 a 转成下标
lower_bound(a + 1, a + n + 1, x) - a
三、upper_bound：第一个 > x 的位置
手写版
cpp
int l = 1, r = n;
int ans = n + 1;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] > x) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
STL 版
cpp
upper_bound(a + 1, a + n + 1, x) - a
四、最后一个等于 x 的位置
思路： 满足 <= x 时往右找，等于 x 时记录答案
cpp
int ans = -1;
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] <= x) {
if (a[mid] == x) ans = mid; // 等于才记录
l = mid + 1;
} else {
r = mid - 1;
}
}
五、常见题型模板
- 求 x 出现的次数
公式：upper_bound - lower_bound
cpp
int l = lower_bound(a+1, a+n+1, x) - a;
int r = upper_bound(a+1, a+n+1, x) - a;
cout << r - l << endl; // 次数 - 区间 [x, y] 内数的个数
第一个 >= x 到 最后一个 <= y
cpp
int left = lower_bound(a+1, a+n+1, x) - a;
int right = upper_bound(a+1, a+n+1, y) - a - 1;
if (left > right) cout << 0;
else cout << right - left + 1; - A-B 数对（差为 C 的数对）
枚举 A，查 B = A - C 的个数
cpp
sort(a+1, a+n+1);
long long ans = 0;
for (int i = 1; i <= n; i++) {
int B = a[i] - C;
int l = lower_bound(a+1, a+n+1, B) - a;
int r = upper_bound(a+1, a+n+1, B) - a;
ans += r - l;
} - 递增三元组（a < b < c）
枚举中间数 b [i]，算 a 中小于它的数量 × c 中大于它的数量
cpp
sort(a+1, a+n+1);
sort(c+1, c+n+1);
long long ans = 0;
for (int i = 1; i <= n; i++) {
long long x = lower_bound(a+1, a+n+1, b[i]) - a - 1; // 小于b[i]的个数
long long y = n - (upper_bound(c+1, c+n+1, b[i]) - c) + 1; // 大于b[i]的个数
ans += x * y;
} - 和为 0 的 4 个值（折半枚举）
n=1000 时 n⁴ 太大，拆成两组 n²，二分查找
cpp
// p 存 A+B，q 存 C+D
sort(q+1, q+id2+1);
long long ans = 0;
for (int i = 1; i <= id1; i++) {
int x = -p[i];
int l = lower_bound(q+1, q+id2+1, x) - q;
int r = upper_bound(q+1, q+id2+1, x) - q;
ans += r - l;
} - 结构体二分（学生信息查询）
按关键字排序，用 lower_bound 查找
cpp
struct stu {
string id, name;
int sex, age;
};
bool cmp(stu a, stu b) { return a.id < b.id; }
// 查找
stu x; shtu = t;
int idx = lower_bound(a+1, a+n+1, x, cmp) - a;
if (a[idx].id == t) { /* 找到 */ }
六、核心口诀
表格
函数 含义
lower_bound 第一个 >= x
upper_bound 第一个 > x
找 "第一个" 满足条件：
满足条件 → 记录 ans，然后 r = mid - 1（往左找更优）
找 "最后一个" 满足条件：
满足条件 → 记录 ans，然后 l = mid + 1（往右找更优）
找不到时：
第一个位置类 → 输出 n + 1
存在性查找 → 输出 -1
重要前提：数组必须有序！ 题目没保证有序时，先排序：
cpp
sort(a + 1, a + n + 1);
这里空空如也
有帮助，赞一个