Day3-二分查找学习笔记
2026-07-23 23:54:02
发布于：广东
Day3-二分查找学习笔记
一、二分查找概念
1. 猜数字小游戏
老师心里想了一个 1 到 100 之间的整数，让你来猜。
如果你从 1 开始一个一个猜：
1, 2, 3, 4, 5, ...
如果答案是 99，就要猜很多次。
更聪明的方法是：
先猜 50
如果答案比 50 大，就只看 51 到 100
再猜 75
如果答案比 75 小，就只看 51 到 74
继续这样猜……
每次都把范围缩小一半，这就是二分查找的想法。
2. 二分核心思想
二分查找的核心思想：
每次看中间位置，根据结果丢掉一半不可能的答案。
也就是说，我们不用一个一个找，而是不断缩小查找范围。
3. 为什么二分要求有序？
二分查找必须用在“有序”的数据中。
例如从小到大排列：
1 3 5 7 9 11 13
如果我们查找 9：
- 先看中间的 7
- 9 比 7 大
- 所以 9 一定在右边
但是如果数组没有排序：
7 1 13 3 9 5 11
看到中间的 3，不能判断 9 一定在左边还是右边。
所以二分查找的前提是：
数组必须有序。
二、普通二分查找
普通二分查找的任务：
在有序数组中查找是否存在 x。
如果存在，输出它的位置；如果不存在，说明没有找到。
1. l、r 的含义
我们用两个变量表示当前查找范围：
int l = 0;
int r = n - 1;
含义是：
当前只在下标 l 到 r 之间查找。
例如：
下标：0 1 2 3 4 5 6
数组：1 3 5 7 9 11 13
一开始：
l = 0, r = 6
表示从整个数组里找。
2. mid 的计算
中间位置：
int mid = (l + r) / 2;
也可以写成更安全的形式：
int mid = l + (r - l) / 2;
初学时先记住：
mid 是当前查找范围的中间位置。
3. 三种情况
假设当前中间位置是 mid，我们比较 a[mid] 和 x。
第一种情况：
if (a[mid] == x)
说明找到了。
第二种情况：
if (a[mid] < x)
说明中间数太小了，答案如果存在，只可能在右边。
所以：
l = mid + 1;
第三种情况：
if (a[mid] > x)
说明中间数太大了，答案如果存在，只可能在左边。
所以：
r = mid - 1;
4. 普通二分查找模板
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main() {
int n, x;
cin >> n >> x;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int l = 1, r = n;
int ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] == x) {
ans = mid;
break;
} else if (a[mid] < x) {
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans << endl;
return 0;
}
说明：
- 如果输出
-1，表示没有找到。 - 这里的下标从
0开始。
三、二分上下界
普通二分只能回答：
x 有没有出现？
但是有时候我们还想知道：
第一个大于等于 x 的数在哪里？
第一个大于 x 的数在哪里？
x 出现了多少次？
区间 [x, y] 中有多少个数？
这时候就需要上下界。
1. 为什么需要上下界？
看这个数组：
1 2 2 2 4 5 7
如果查找 2，普通二分可能找到中间某一个 2，但不一定是第一个 2。
我们有时需要找到：
第一个 >= 2 的位置
如果按从 1 开始编号，这个位置就是第 2 个数。
也可能需要找到：
第一个 > 2 的位置
如果按从 1 开始编号，这个位置就是第 5 个数。
这一章我们先不使用 C++ 自带函数，而是学习自己手写。
为了和课堂模板一致，下面的代码使用：
数组下标从 1 开始，范围是 a[1] 到 a[n]
2. 找第一个大于等于 x 的位置
我们要找的是：
第一个 >= x 的位置
例如：
位置：1 2 3 4 5 6 7
数组：1 2 2 2 4 5 7
x = 2
第一个 >= 2 的位置是 2
再例如：
位置：1 2 3 4 5 6 7
数组：1 2 2 2 4 5 7
x = 3
第一个 >= 3 的位置是 5，因为 a[5] = 4
3. 左右区域划分
我们想把数组分成两部分：
左边：< x
右边：>= x
我们要找的是右边区域的第一个位置。
例如查找第一个 >= 3：
位置：1 2 3 4 | 5 6 7
数组：1 2 2 2 | 4 5 7
左边 <3 右边 >=3
答案是位置 5。
4. 手写模板：找第一个大于等于 x
int l = 1, r = n;
int ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] >= x) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans << endl;
注意：
ans表示目前找到的可能答案。- 如果最后
ans还是-1，表示没有找到大于等于x的数。 - 因为要输出答案，所以在完整程序里用
cout << ans << endl;。
5. 边界怎么移动？
当：
a[mid] >= x
说明 mid 这个位置符合要求，它可能就是答案。
但是我们要找的是“第一个”符合要求的位置，所以还要继续往左找。
所以：
ans = mid;
r = mid - 1;
当：
a[mid] < x
说明 mid 太小了，不可能是答案，答案只能在右边。
所以：
l = mid + 1;
6. 不存在的情况
例如：
数组：1 2 4 5 7
x = 10
没有任何数 >= 10。
这时 ans 一直不会被修改，最后还是：
-1
7. 找第一个大于 x 的位置
现在我们换一个问题：
第一个 > x 的位置
例如：
位置：1 2 3 4 5 6 7
数组：1 2 2 2 4 5 7
x = 2
第一个 > 2 的位置是 5
8. 左右区域划分
我们想把数组分成两部分：
左边：<= x
右边：> x
我们要找的是右边区域的第一个位置。
例如查找第一个 > 2：
位置：1 2 3 4 | 5 6 7
数组：1 2 2 2 | 4 5 7
左边 <=2 右边 >2
答案是位置 5。
9. 手写模板：找第一个大于 x
int l = 1, r = n;
int ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] > x) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans << endl;
10. 边界怎么移动？
当：
a[mid] > x
说明 mid 这个位置符合要求，它可能就是答案。
但是我们要找的是“第一个”符合要求的位置，所以继续往左找。
所以：
ans = mid;
r = mid - 1;
当：
a[mid] <= x
说明 mid 不够大，不可能是答案，答案只能在右边。
所以：
l = mid + 1;
11. 两种上下界区别总结
| 要找什么 | 判断条件 | 找到后怎么做 | 不符合时怎么做 |
|---|---|---|---|
第一个 >= x |
a[mid] >= x |
ans = mid; r = mid - 1; |
l = mid + 1; |
第一个 > x |
a[mid] > x |
ans = mid; r = mid - 1; |
l = mid + 1; |
最重要的区别：
找第一个 >= x，看 a[mid] >= x
找第一个 > x，看 a[mid] > x
12. 课堂记忆方法
这两个模板长得几乎一样，只差一个判断条件：
if (a[mid] >= x) // 第一个大于等于 x
或者：
if (a[mid] > x) // 第一个大于 x
其他部分都可以先照着同一个模板写。
完整记忆：
找到一个可能答案，就先记到 ans 里；
但因为要找第一个，所以继续往左边找。
四、STL 二分函数
C++ 已经帮我们写好了二分查找函数。
使用前需要：
#include <bits/stdc++.h>
using namespace std;
1. lower_bound()
格式：
lower_bound(a + 1, a + n + 1, x)
含义：
在数组 a 中找第一个 >= x 的位置。
2. upper_bound()
格式：
upper_bound(a + 1, a + n + 1, x)
含义：
在数组 a 中找第一个 > x 的位置。
3. 返回值转换成下标
STL 的 lower_bound() 和 upper_bound() 返回的不是普通整数下标，而是一个“位置指针”。
要转换成下标，可以这样写：
int pos = lower_bound(a + 1, a + n + 1, x) - a;
或者：
int pos = upper_bound(a + 1, a + n + 1, x) - a;
4 查找第一个 >= x 的位置
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main() {
int n, x;
cin >> n >> x;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int pos = lower_bound(a + 1, a + n + 1, x) - a;
if (pos == n + 1) {
cout << -1 << endl;
} else {
cout << pos << endl;
}
return 0;
}
5 查找第一个 > x 的位置
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main() {
int n, x;
cin >> n >> x;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int pos = upper_bound(a + 1, a + n + 1, x) - a;
if (pos == n + 1) {
cout << -1 << endl;
} else {
cout << pos << endl;
}
return 0;
}
五、二分查找易错点
1. 忘记数组必须有序
错误想法：
任何数组都能二分。
正确想法：
只有有序数组才能二分。
如果题目没有保证有序，可能需要先排序：
sort(a + 1, a + n + 1);
2. l、r 的范围写错
普通二分常用：
int l = 0, r = n - 1;
while (l <= r)
上下界二分常用：
int l = 0, r = n;
while (l < r)
不要把两个模板混在一起乱改。
3. mid 写错
推荐写法：
int mid = l + (r - l) / 2;
4. 更新边界时漏掉 1
普通二分中：
l = mid + 1;
r = mid - 1;
因为 mid 已经检查过了。
上下界二分中：
r = mid;
l = mid + 1;
因为 mid 有时可能就是答案，不能随便丢掉。
5. 忘记判断 pos == n + 1
例如：
int pos = lower_bound(a + 1, a + n + 1, x) - a;
如果 pos == n + 1，说明没有找到符合条件的位置。
不能直接访问：
a[pos]
否则会访问到数组外面。
6. 下标从 0 开始还是从 1 开始
C++ 普通数组的下标一般从 0 开始。
如果题目要求输出第几个数，可能要输出：
pos + 1
如果题目要求输出下标，通常输出：
pos
读题时一定要看清楚。
六、二分综合应用总结
1. 常见问题和方法
| 问题 | 方法 |
|---|---|
| 查找 x 是否存在 | 普通二分 |
找第一个 >= x |
lower_bound |
找第一个 > x |
upper_bound |
| 统计 x 出现次数 | upper_bound(x) - lower_bound(x) |
统计 [x, y] 中数量 |
upper_bound(y) - lower_bound(x) |
2. 记忆口诀
数组有序才能分，
每次都看中间人。
小了右边继续找，
大了左边别乱跑。
lower 找到第一个 >=，
upper 找到第一个 >。
3. 推荐背诵模板
普通二分：
int l = 0, r = n - 1;
int ans=-1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] == x) {
ans=mid;
} else if (a[mid] < x) {
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans << endl;
第一个 >= x：
int pos = lower_bound(a + 1, a + n + 1, x) - a;
第一个 > x：
int pos = upper_bound(a + 1, a + n + 1, x) - a;
统计 x 的个数：
int cnt = upper_bound(a + 1, a + n + 1, x) - lower_bound(a + 1, a + n + 1, x);
统计 [x, y] 的个数：
int cnt = upper_bound(a + 1, a + n + 1, y) - lower_bound(a + 1, a + n + 1, x);
- 二分查找必须用在有序数组中。
lower_bound找第一个>= x的位置。upper_bound找第一个> x的位置。
有帮助，赞一个