整数二分（最常用）
理论图简：
一般二分应用于无非下面这四种情况:
1：找大于等于数的第一个位置 （满足某个条件的第一个数）
2：找小于等于数的最后一个数 （满足某个条件的最后一个数）
3.查找最大值 （满足该边界的右边界）、
4.查找最小值 (满足该边界的左边界)
然后每次使用这这两个模板的时候，先想是找这个区间的左端点还是还是右端点，然后选择用模板
查找左边界
int sl(int l , int r , int x) { while(l < r) { int mid = l + r >> 1; if(q[mid] >= x) r = mid; else l = mid + 1; } return l; }
查找右边界
int sr(int l , int r , int x) { while(l < r) { int mid = r + l + 1 >> 1; if(q[mid] <= x) l = mid; else r = mid - 1; } return r; }
例题
给定一个按照升序排列的长度为 n 的整数数组，以及 q个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1。
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -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
#include<iostream> using namespace std; const int N=1000010; int q[N]; int sl(int l,int r,int x) { while(l<r) { int mid=l+r>>1; if(q[mid]>=x)r=mid; else l=mid+1; } return l; } int sr(int l,int r,int x) { while(l<r) { int mid=r+l+1>>1; if(q[mid]<=x)l=mid; else r=mid-1; } return r; } int main() { int n,m; 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=sl(0,n-1,x);//查找左边界 并返回下标l if(q[l]!=x)cout <<"-1 -1"<<endl;//如果找不到 返回-1 -1 else { cout<<l<<' ';//如果找到了 输出左下标 cout<<sr(0,n-1,x)<<endl;//输出右下标 } } return 0; }
