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.