华师一附中OI组

标题: 1894: 二分查找左侧边界 [打印本页]

---

作者: admin    时间: 2021-11-7 12:18
标题: 1894: 二分查找左侧边界
找自由边界

---

作者: admin    时间: 2021-11-7 12:19

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int mn=1E5+10;
   
4. int a[mn],i,n,q,x;
   
5. int main()
   
6. {
   
7.         cin>>n;
   
8.         for (i=1; i<=n; i++) cin>>a[i];
   
9.         cin>>q;
   
10.         while (q--)
    
11.                 {
    
12.                         cin>>x;
    
13.                         int t=lower_bound(a+1,a+1+n,x)-a;
    
14.                         if (a[t]==x)cout<<t;
    
15.                         else cout<<-1;
    
16.                         cout<<' ';
    
17.                 }
    
18.         return 0;
    
19. }

复制代码

---

作者: admin    时间: 2021-11-7 12:24

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int mn=1E5+10;
   
4. int a[mn],i,n,q,x;
   
5. int main()
   
6. {
   
7.         cin>>n;
   
8.         for (i=1; i<=n; i++) cin>>a[i];
   
9.         cin>>q;
   
10.         while (q--)
    
11.                 {
    
12.                         cin>>x;
    
13.                         int l=1,r=n,ans=-1,m;
    
14.                         while (l<=r)
    
15.                                 {
    
16.                                         m=(l+r)/2;
    
17.                                         if (a[m]==x)
    
18.                                                 {
    
19.                                                         ans=m,r=m-1;
    
20.                                                 }
    
21.                                         else if (a[m]>x) r=m-1;
    
22.                                         else if (a[m]<x) l=m+1;
    
23.                                 }
    
24.                         cout<<ans<<' ';
    
25.                 }
    
26.         return 0;
    
27. }

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2