Run Code  | API  | Code Wall  | Misc  | Feedback  | Login  | Theme  | Privacy  | Patreon 

First and last Occurence of an Element

#include <bits/stdc++.h>
using namespace std;

int main() {
    //code
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        vector<int>v(n);
        for(int i=0;i<n;i++)
          cin>>v[i];
         int s=0;
         int e=n-1;
         int f1=n+1;//first occurence
         int  f2=-1;//last occurence
         int mid;
         while(s<=e)
         {
              mid=s+(e-s)/2;
             if(v[mid]==k)
             { 
                 if(v[mid-1]<k)
                 {
                     f1=mid;
                     break;
                 }
                 else if(v[mid-1]==k)
                 {
                     e=mid-1;
                 }
                 
                 
             }
             else if(v[mid]>k)
             {
                 e=mid-1;
             }
             else if(v[mid]<k)
             {
                 s=mid+1;
             }
         }
         s=0;
         e=n-1;
         while(s<=e)
         {
              mid=s+(e-s)/2;
              if(v[mid]==k)
              {
                  if(v[mid+1]==k)
                  {
                      s=mid+1;
                  }
                  else if(v[mid+1]>k)
                  {
                      f2=mid;
                      break;
                  }
              }
              else if(v[mid]>k)
              {
                  e=mid-1;
              }
              else if(v[mid]<k)
              {
                  s=mid+1;
                  
              }
             
         }
         if(s>e)
         {
             cout<<"-1"<<endl;
         }
         else
         cout<<f1<<" "<<f2<<endl;
    }
    return 0;
}
 run  | edit  | history  | help 0