2023.9.14 整数二分排序

 1 # 二分
 2 
 3 ## 整数二分
 4 
 5 ~~~c++
 6 //区间[l,r]被划分成[l,mid]和[mid+1,r]时使用
 7 int test01(int l,int r)
 8 {
 9     while(l<r)
10     {
11         int mid = (l+r)/2;
12         bool check(int mid);//check判断mid是否满足x性质
13         if(check(mid)) r = mid;//mid满足，即要找的x在[l,mid]区间内
14         else l = mid +1;//mid不满足，即要找的x在[mid+1,r]区间内
15     }
16     return 1;
17 }
18 //区间[l,r]被划分成[l,mid-1]和[mid,r]时使用
19 int test02(int l,int r)
20 {
21     while(l<r)
22     {
23         int mid = (1+r+1)/2;//mid - 1 = (l+r)/2;
24         bool check(mid);
25         if(check(mid)) l = mid;
26         else r = mid-1;
27     }
28 }
29 ~~~
30 
31 ~~~c++
32 #include <iostream>
33 using namespace std;
34 const int N = 10e6+10;
35 int m, n;
36 int q[N];
37 
38 int main()
39 {
40     cin >> n>>m;
41     for (int i = 0; i < n; i++)  cin >> q[i];
42     
43     while (m--)
44     {
45         int x; cin >> x;
46         int l = 0;
47         int r = n - 1;
48         while (l < r)
49         {
50             int mid = (l + r)/2;
51             if (q[mid] >= x) r = mid;
52             else l = mid + 1;
53         }//判断第一种边界情况
54         if (q[l] != x) cout << "-1 -1" << endl;
55         else
56         {
57             cout << l << " ";
58             int l = 0, r = n - 1;
59             while (l < r)
60             {
61                 int mid = (l + r + 1)/2;
62                 if (q[mid] <= x) l = mid;
63                 else r = mid - 1;
64             }//判断第二种边界情况
65             cout << l << endl;
66         }
67     }
68     return 0;
69 }