23-5-12--二分查找--二分查找模板

daniel350-wang / 2023-05-14 / 原文

 1 #include <stdio.h>
 2 //#include <iostream>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 struct array {
 8     long long index;
 9     long long num;
10 };
11 
12 bool cmp(array x,array y)
13 {
14 return x.num<y.num;
15 }
16 
17 int main()
18  
19 {
20       long long n,q;
21      scanf("%lld %lld",&n,&q);
22      struct array a[n];
23      long long i,j;
24      for(i=0;i<n;i++)
25      {
26          a[i].index = i+1;
27          scanf("%lld",&a[i].num );
28      }
29      sort(a,a+n,cmp);
30 
31      for(i=0;i<q;i++)
32      {
33          long long x;
34          scanf("%lld",&x);
35          long long mid;
36          long long high=n-1,low=0;
37          while(low<=high)
38          {
39              mid=(high+low)/2;
40              if(a[mid].num >x)
41              {
42                  high=mid-1;
43              }else if(a[mid].num <x)
44              {
45                  low=mid+1;
46                  
47              }else if(a[mid].num ==x)
48              {
49                  break; 
50              }
51         }
52         printf("%lld\n",a[mid].index );
53      }
54      
55 }