tungggg

first and last pos _ binary search

Apr 4th, 2022
41
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.84 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int key ;
  5.  
  6. int first_pos(int * a, int n, const int *key  ){
  7.     int res =-1 ;
  8.     int l=0, r=n-1;
  9.    
  10.     while ( l<= r ){
  11.         int mid = (l+r)/2;
  12.         if ( a[mid]== *key ){
  13.             res= mid;
  14.             r=mid-1;
  15.         }
  16.         else if ( *key > a[mid] ){
  17.             l=mid+1;
  18.             continue;
  19.         }
  20.         else{
  21.             r=mid-1;
  22.             continue ;
  23.         }
  24.     }
  25.     return res;
  26. }
  27.  
  28. int last_pos(int *a , int n, const int *key  ){
  29.    
  30.     int res=-1;
  31.     int l =0 , r= n-1;
  32.     while( l<=r ){
  33.         int mid= (l+r)/2;
  34.         if ( *key == a[mid] ){
  35.             res=mid ;
  36.             l=mid+1;
  37.         }
  38.         else if ( *key > a[mid] ){
  39.             l=mid+1;
  40.         }
  41.         else {
  42.             r=mid-1;
  43.         }
  44.     }
  45.     return res;
  46. }
  47.  
  48.  
  49. int main(){
  50.     int n;
  51.     cin >> n;
  52.     int *a = new int [n];
  53.     for (int i=0;i<n;i++) cin >> a[i];
  54.     sort(a,a+n);
  55.     cin >> key ;
  56.     cout<<first_pos(a,n,&key)<<endl<<last_pos(a,n,&key)<<endl;
  57.     return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment