B1894 【入门】二分查找左侧边界
大约 2 分钟
B1894 【入门】二分查找左侧边界
【算法】 二分查找
【C++】 二分查找、lower_bound
【难度】 普及−
B1894 【入门】二分查找左侧边界
一、题目简述
有一个有序不递减数组(元素可以重复),需要回答 次询问。每次询问给一个整数 ,要求找出 在数组中第一次出现的位置(下标从 1 开始)。如果 不存在,则输出 -1。
数据范围:。
二、解题思路
这是一道经典的左侧边界二分查找问题,本质就是实现 STL 中的 lower_bound。
二分策略
我们要找的是第一个 的位置,最后再检查该位置是否等于 。
维护区间 ,初始 。当 时循环:
- 取中点
- 如果 ,说明答案在 中,令
- 否则 ,说明答案在 中,令
循环结束后 ,判断 是否等于 即可。
注意:这里用 mid = (l+r)/2(下取整),配合 r = mid 的收缩方式,不会出现死循环。
为什么不能用 while (l <= r)?
while (l < r) 的写法退出时 ,恰好锁定唯一候选位置。如果用 while (l <= r),退出时 ,反而不方便判断。
STL 写法
直接使用 lower_bound(a+1, a+n+1, x) 返回第一个 的迭代器,减去数组首地址即得下标。
手动模拟
数组 ,查找 :
| 步骤 | l | r | mid | a[mid] | 比较 | 操作 |
|---|---|---|---|---|---|---|
| 1 | 1 | 6 | 3 | 2 | 2 ≥ 2 | r = 3 |
| 2 | 1 | 3 | 2 | 2 | 2 ≥ 2 | r = 2 |
| 3 | 1 | 2 | 1 | 1 | 1 < 2 | l = 2 |
,,答案为 2。正确找到了第一个 2 的位置。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
int l = 1, r = n;
while (l < r) {
int mid = (l + r) / 2;
if (a[mid] >= x)
r = mid;
else
l = mid + 1;
}
if (a[l] == x)
cout << l << " ";
else
cout << -1 << " ";
}
return 0;
}四、复杂度分析
- 时间复杂度:每次询问二分查找 ,共 次询问,总复杂度 。
- 空间复杂度:数组 大小 ,。
五、知识扩展
二分查找的两种经典写法对比:
| 目标 | mid 取法 | 收缩方式 |
|---|---|---|
| 左侧边界(第一个 ≥ x) | mid = (l+r)/2 | a[mid] ≥ x → r = mid |
| 右侧边界(最后一个 ≤ x) | mid = (l+r+1)/2 | a[mid] ≤ x → l = mid |
关键在于避免死循环:当 时,下取整的 mid 会等于 。如果此时收缩方式是 l = mid,就会导致 不变,出现死循环。因此右侧边界二分需要上取整,即 mid = (l+r+1)/2。
