宝安网站建设深圳信科,南昌做网站kaiu,建设视频网站要求,北京天津网站建设给定一个按照升序排列的长度为 n 的整数数组#xff0c;以及 q 个查询。
对于每个查询#xff0c;返回一个元素 k 的起始位置和终止位置#xff08;位置从 0 开始计数#xff09;。
如果数组中不存在该元素#xff0c;则返回 -1 -1。
输入格式 第一行包含整数 n 和 q 以及 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 二分的本质就是 我们可以找到一种性质使一个东西一分为二并且可以找到两部分的边界。 1二分红色边界 下面这行:更新的时候mid 属于l的就1因为C下取整防止死循环 mid (l r 1) / 2 2二分绿色边界 mid (l r) / 2 找第一个x性质定义为q[mid] x。 找第二个x性质定义为q[mid] x。
#include iostreamusing namespace std;const int N 100010;
int n, q;
int a[N];int main ()
{scanf(%d%d, n, q);for(int i 0; i n; i ) scanf(%d, a[i]);while(q -- ){int x;scanf(%d, x);int l 0, r n - 1;while(l r){int mid l r 1;if(a[mid] x) r mid;else l mid 1;}if(a[l] ! x) {printf(-1 -1\n);}else{printf(%d , l);int l 0, r n - 1;while(l r){int mid l r 1 1; if(a[mid] x) l mid; // 因为是左边满足check更新成mid上面取mid加1else r mid - 1;}printf(%d\n, l);}}return 0;
}
