题目：
给定一个按照升序排列的长度为 n 的整数数组，以及 q个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 00 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n个整数（均在 1∼100001∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤1000001
1≤q≤10000
1≤k≤10000
输入样例：
6 3 1 2 2 3 3 4 3 4 5
输出样例：
3 4 5 5 -1 -1
二分法思想
1、二分法就是寻找一个边界。该边界的左边满足一个性质，右边满足另外一个性质。同时两个性质是对立的，即如果不满足左边区域的数一定满足右边区域。
2、二分法每次循环能排除约一半的数据量（每次只选择一边继续查找），所以整体的时间复杂度只有O（nlogn）
3、二分法的关键在于左右边性质的确定以及mid值的确定。
图解二分法
前叙：
1、首先看中间的两个箭头，这两个箭头实际上是指我们要确认的边界。这个边界可以是一个具体要找到的一个数，也可以是一个性质的边界。
2、左右两边就是被这个边界分割开的两个区域。mid此时可能落在左右任何一个地方。落在左边和右边的处理方法不同
具体步骤：
1、确认左右区域所对应的性质。例如本题左边是小于x，右边是大于x。
2、确认x边界属于左边还是右边。例如本题找起始位置时，由于右边仍可能有x相同值，所以让x属于右区域。（若让其属于左区域，则两边的范围都将包括x，那么就是非对立了）
3、根据性质，具体去看是变化L，还是变化R。总共两者变化方式1、l=mid，r=mid-1 2、l=mid+1,r=mid
4、如果是l=mid的情况将mid的值改为（l+r+1）/2。如果是l=mid+1则mid值为（l+r）/2
本题代码：
#include<iostream> using namespace std; int main(){ int num[100001]={0}; int k,q,n=0; //k表示查询得数，q表示要查询多少个数,n表示数组中有多少数 cin>>n>>q; for(int i=0;i<n;i++){ scanf("%d",&num[i]); } while(q--){ //找起始位置 cin>>k; int l=0; int r=n-1; while(l<r){ int mid=(l+r)>>1; if(num[mid]>=k)r=mid; else l=mid+1; } if(num[l]!=k){ cout<<"-1 -1"<<endl; } else{ cout<<l<<" "; //当起始位置存在且找到后，我们再去寻找结束位置 l=0;r=n-1; while(l<r){ int mid=(l+r+1)>>1;//l=mid决定其要格外加1（当l=r-1时不加1死循环） if(num[mid]<=k)l=mid; else r=mid-1; } cout<<l<<endl; } } }
二分法背诵模板：
//查找左边界 SearchLeft 简写SL int SL(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } return l; } //查找右边界 SearchRight 简写SR int SR(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; //需要+1 防止死循环 if (check(mid)) l = mid; else r = mid - 1; } return r; }
模板记忆
记忆方面：
来自视频评论区下方的一句话 : 有加必有减
int mid = l + r + 1 (加)>> 1;
if (check(mid)) l = mid;
else r = mid - 1 (减);
图解
左边界 ：边界最左边的那个数 右边界同理。
一般二分应用于无非下面这四种情况:
1：找大于等于数的第一个位置 （满足某个条件的第一个数）
2：找小于等于数的最后一个数 （满足某个条件的最后一个数）
3.查找最大值 （满足该边界的右边界）、
4.查找最小值 (满足该边界的左边界)
