整数二分

整数二分

两个板子 主要通过check来判断使用哪个板子 int l=0,r=n-1; while(l<r) { int mid = r+l>>1; if(check(mid)) r=mid; else l=mid+1; } int l=0,r=n-1; while(l<r) { int mid = r+l+1>>1; if(check(mid)) l=mid; else r=mid-1; }

代码

给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。 对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。 如果数组中不存在该元素，则返回“-1 -1”。 输入格式 第一行包含整数n和q，表示数组长度和询问个数。 第二行包含n个整数（均在1~10000范围内），表示完整数组。 接下来q行，每行包含一个整数k，表示一个询问元素。 输出格式 共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。 如果数组中不存在该元素，则返回“-1 -1”。 数据范围 1≤n≤1000001≤n≤100000 1≤q≤100001≤q≤10000 1≤k≤100001≤k≤10000 输入样例： 6 3 1 2 2 3 3 4 3 4 5 输出样例： 3 4 5 5 -1 -1 #include<bits/stdc++.h> using namespace std; const int N=100010; int q[N]; int n,m; int main() { scanf("%d %d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&q[i]); while(m--) { int x; scanf("%d",&x); //找左边界 int l=0,r=n-1; while(l<r) { int mid = r+l>>1; if(q[mid]>=x) r=mid; else l=mid+1; } if(q[l]!=x) cout<<"-1 -1"<<endl; else { //找右边 cout<<l<<" "; int l=0,r=n-1; while(l<r) { int mid=r+l+1>>1; if(q[mid]<=x) l=mid; else r=mid-1; } cout<<l<<endl; } } return 0; }