789. 数的范围

789. 数的范围

文章目录

​​Question​​​​Ideas​​​​Code​​

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

整数二分

Code

n,m = list(map(int,input().strip().split()))lis = list(map(int,input().strip().split()))for i in range(m): x = int(input()) l,r = 0,n-1 while l < r: mid = l + r >> 1 if lis[mid] >= x: r = mid else: l = mid + 1 # 二分一定有答案，但是答案不一定符合题目要求 if lis[l] != x: print(-1,-1) else: print(l,end=' ') r = n-1 while l < r: mid = l + r + 1 >> 1 if lis[mid] <= x: l = mid else: r = mid - 1 print(r)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。