二分模板 Acwing 789 数的范围

二分一定有解，若出现无解，一定是题目中无解二分步骤：定义check函数，先找到一个x，使得区间左边满足条件区间右边不满足条件，

定义mid = l + r >> 1去判断于x的关系，此时需要判断边界关系，例如当a[mid]小于x时，说明二分值在x的左边，此时缩小范围为【mid，r】，

即令 l = mid,此时返回check函数，使 mid = l + r +1 >> 1,因为在这里mid是向下取整，不加一的话，当 l  = r - 1是 ，mid = l,此时循环后的区间

还是【l,r】,会形成死循环，所以 + 1后范围会变成 mid = r ,得到我们的x的第一次出现的值，在循环最后一次，我们的 l 和 r都在x 的两侧

此时 l = r = x,因此当无解时，判断最后一轮a[ l ] != x ，即为无解，此题要判断两次，所以再进行一次二分，判断x的结束的位置，以下为代码

 1 #include<iostream>
 2 using namespace std;
 3 
 4 const int N = 100010;
 5 int n,m;
 6 int a[N];
 7 
 8 int main()
 9 {
10     scanf("%d%d", &n, &m);
11     for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
12     
13     while (m -- )
14     {
15         int x,l = 0, r = n - 1;
16         scanf("%d", &x);
17         
18         while(l < r)
19         {
20             int mid = l + r >> 1;
21             if(a[mid] >= x) r = mid;
22             else l = mid + 1;
23         }
24         if(a[l] != x) cout <<"-1 -1" << endl;
25         
26         else
27         {
28             cout << l << ' ';
29             
30             int l = 0,r = n - 1;
31             
32             while(l < r)
33             {
34                 int mid = l + r + 1>> 1;
35                 if(a[mid] <= x)  l = mid ;
36                 else r = mid - 1;
37             }
38             cout << l << endl;
39         }
40     }
41     return 0;
42 }