Advertisement
Fahim_7861

Binary search using vector pair

Jun 21st, 2018
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.20 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<ll,ll>pll;
  5. typedef pair<ll,pair<ll,ll> >pk;
  6. #define sf(a) scanf("%d",&a)
  7. #define pf(a) printf("%d\n",a)
  8. #define F first
  9. #define S second
  10. #define minheap int,vector<int>,greater<int>
  11. #define mp make_pair
  12. #define pb push_back
  13. #define pp pop_back
  14. #define ischar(x) (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
  15. #define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
  16. const int Max = 2e6 + 10;
  17. const int Mod = 1e9 + 7;
  18. bool compare(const pair<int,int> &a,
  19. const pair<int,int> &b)
  20. {
  21. return (a.second > b.second);
  22. }
  23. ll b_search(vector<pll>ara,int low,int high,int k)
  24. {
  25. while(low<=high)
  26. {
  27. int mid=(low+high)/2;
  28. if(ara[mid].F==k) return mid;
  29. if(k>ara[mid].F) low=mid+1;
  30.  
  31. else high=mid-1;
  32. }
  33. return -1;
  34. }
  35.  
  36. int main()
  37. {
  38. fastread();
  39.  
  40.  
  41. vector<pll>v;
  42. int i,n,k;
  43. cin>>n;
  44.  
  45. for(i=0; i<n; i++)
  46. {
  47. cin>>k;
  48.  
  49. v.pb(mp(k,i));
  50. }
  51.  
  52. sort(v.begin(),v.end());
  53.  
  54. cin>>k;
  55.  
  56.  
  57. int sum=b_search(v,0,n-1,k);
  58.  
  59. if(sum==-1)cout<<"Not found\n";
  60.  
  61. else cout<<v[sum].S<<endl;
  62.  
  63. cout<<endl;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement