B1895 【入门】二分查找右侧边界
大约 2 分钟
B1895 【入门】二分查找右侧边界
【算法】 二分查找
【C++】 二分查找、upper_bound
【难度】 普及−
B1895 【入门】二分查找右侧边界
一、题目简述
有一个有序不递减数组(元素可以重复),需要回答 次询问。每次询问给一个整数 ,要求找出 在数组中最后一次出现的位置(下标从 1 开始)。如果 不存在,则输出 -1。
数据范围:。
二、解题思路
这道题是右侧边界二分查找问题,本质是 upper_bound 减 1。
二分策略
我们要找的是最后一个 的位置。
维护区间 ,初始 。当 时循环:
- 取中点 (注意是上取整)
- 如果 ,说明答案在 中,令
- 否则 ,说明答案在 中,令
循环结束后 ,判断 是否等于 即可。
为什么必须上取整?
当区间缩减到 时,下取整的 mid = (l+r)/2 会等于 。如果此时 ,收缩方式为 , 不会改变,导致死循环。
改为 mid = (l+r+1)/2(上取整),此时 ,收缩 ,区间收敛。
STL 写法
upper_bound(a+1, a+n+1, x) 返回第一个 的位置,减 1 就是最后一个 的位置。再检查该位置是否等于 。
int pos = upper_bound(a + 1, a + n + 1, x) - a - 1;
if (pos >= 1 && a[pos] == x) cout << pos << " ";
else cout << -1 << " ";手动模拟
数组 ,查找 :
| 步骤 | l | r | mid | a[mid] | 比较 | 操作 |
|---|---|---|---|---|---|---|
| 1 | 1 | 6 | 4 | 2 | 2 ≤ 2 | l = 4 |
| 2 | 4 | 6 | 5 | 3 | 3 > 2 | r = 4 |
,,答案为 4。正确找到了最后一个 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 + 1) / 2; // 上取整
if (a[mid] <= x)
l = mid;
else
r = mid - 1;
}
if (a[l] == x)
cout << l << " ";
else
cout << -1 << " ";
}
return 0;
}四、复杂度分析
- 时间复杂度:每次询问二分查找 ,共 次询问,总复杂度 。
- 空间复杂度:数组 大小 ,。
五、知识扩展
右侧边界二分的 mid 上取整是很多初学者容易忽略的细节。一个小技巧可以帮助记忆:
- 如果收缩时写的是
l = mid(左侧不动,右侧往左靠),就用上取整 - 如果收缩时写的是
r = mid(右侧不动,左侧往右靠),就用下取整
这样就能保证每次循环区间都会严格缩小,不会死循环。
