整数二分
二分本质并不是数据单调性
本质为:给定一个区间,在区间上定义了某种性质,使得这个性质在左(右)半边是满足的,在右(左)半边是不满足的,二分就可以寻找这个性质的边界
红色的整数二分
- 确定中间值:mid =
l + r + 1
>> 1 - 检测中间值的性质(对应的是绿色区域的性质,即不满足整个区间的性质):
check(q[mid])
- 如果为
true
,mid
就在红色区间里,res
就在[mid, r]
- 如果为
false
,mid
就在绿色区间里,res
就在[l, mid - 1]
- 更新方式
- 如果上面的判断为
true
,l = mid
- 如果上面的判断为
false
,r = mid - 1
绿色的整数二分
- 确定中间值:mid =
l + r
>> 1 - 检测中间值的性质(对应的是红色区域的性质,即不满足整个区间的性质):
check(q[mid])
- 如果为
true
,mid
就在绿色区间里,res
就在[l, mid]
- 如果为
false
,mid
就在红色区间里,res
就在[mid + 1, r]
- 更新方式
- 如果上面的判断为
true
,r = mid
- 如果上面的判断为
false
,l = mid + 1
n, q = list(map(int,input().split()))
alist = list(map(int,input().split()))
# q[mid] >= x
def searchLeft(q, l, r, k):
while l < r:
mid = l + r >> 1
if q[mid] >= k: r = mid
else: l = mid + 1
return l
# q[mid] <= x
def searchRight(q, l, r, k):
while l < r:
mid = l + r + 1 >> 1
if q[mid] <= k: l = mid
else: r = mid - 1
return l
while q:
q -= 1
k = int(input())
l = searchLeft(alist, 0, n - 1, k)
if alist[l] != k:
print('-1 -1')
else:
r = searchRight(alist, 0, n - 1, k)
print(l, r)