789. 数的范围(二分)
二分 范围
2023-09-14 09:14:58 时间
蓝桥杯国赛指南,详情见专栏
Question
给定一个按照升序排列的长度为 n 的整数数组,以及 q 个查询。
对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 0 开始计数)。
如果数组中不存在该元素,则返回 -1 -1。
输入格式
第一行包含整数 n 和 q,表示数组长度和询问个数。
第二行包含 n 个整数(均在 1∼10000 范围内),表示完整数组。
接下来 q 行,每行包含一个整数 k,表示一个询问元素。
输出格式
共 q 行,每行包含两个整数,表示所求元素的起始位置和终止位置。
如果数组中不存在该元素,则返回 -1 -1。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例:
6 3
1 2 2 3 3 4
3
4
5
输出样例:
3 4
5 5
-1 -1
Ideas
数据范围1e5考虑二分
二分要满足两个条件:
- 二段性 即一半区间满足条件,另外一段区间不满足条件,本题的条件就是a[m] >= x
- 模板 绿右左右:求右边区间的左端点,更新r
如果更新l=m,l+r+1>>1
Code
n,m = list(map(int,input().strip().split()))
a = list(map(int,input().strip().split()))
for i in range(m):
x = int(input())
l,r = 0, n-1
# 求左区间
while l < r:
m = l + r >> 1
if a[m] >= x:
r = m
else:
l = m + 1
if a[l] == x:
print(l,end=' ')
# 求右区间
r = n - 1
while l < r:
m = l + r + 1>> 1
if a[m] <= x:
l = m
else:
r = m - 1
print(r)
else:
print(-1,-1)