Search in a Rotated Array

QUESTION

Given a sorted and rotated array (rotated at some point) A[ ], and given an element K, the task is to find the index of the given element K in the array A[ ]. The array has no duplicate elements. If the element does not exist in the array, print -1.\n \n\nInput:\nThe first line of the input contains an integer T, depicting the total number of test cases. Then T test cases follow. Each test case consists of three lines. First line of each test case contains an integer N denoting the size of the given array. Second line of each test case contains N space separated integers denoting the elements of the array A[ ]. Third line of each test case contains an integer K denoting the element to be searched in the array.\n\n\nOutput:\n\nCorresponding to each test case, print in a new line, the index of the element found in the array. If element is not present, then print -1.\n\nConstraints:\n\n1<=T<=100\n1<=N<=100005\n0<=A[i]<=10000005\n1<=k<=100005.

“TESTCASE_1”: “3\n9\n5 6 7 8 9 10 1 2 3\n10\n3\n3 1 2\n1\n4\n3 5 1 2\n6\n###—###SEPERATOR—###—\n5\n1\n-1”, “TESTCASE_2”: “3\n7\n5 7 9 11 13 15 17 \n10\n4\n4 1 1 2\n1\n4\n3 5 1 2\n6\n###—###SEPERATOR—###—\n-1\n2\n-1”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include <iostream>
using namespace std;
int main()
{
 int m,n,i,j,a[10000],s;
  cin>>m;
 for(int k=0;k<m;k++)
 {
   cin>>n;
  for(i=0;i<n;i++)
  {
     cin>>a[i];
  }
  cin>>s;
  for(i=0;i<n;i++)
  {
      if(s==a[i])
       { 
          for(j=i+1;j<n;j++)
             { //cout<<"hi2";
                if(a[i]==a[j])
                    { //cout<<"hi3";
                       cout<<j<<endl;
                       break;
                    }
          }
                if(j==n)
                    { 
                       cout<<i<<endl;
                       break;
                    }
            break;  
         }
    }
    
  
    if(i==n)
    { //cout<<"hi5";
       cout<<"-1"<<endl;
    }
   
    
  
  
 }
	return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro