 39

# Search In Rotated Sorted Array

Difficulty: MEDIUM Contributed By
Prateek Kalyani
Avg. time to solve
30 min
Success Rate
65%

Problem Statement
Suggest Edit

#### After rotating a sorted array, Aahad needs to answer Q queries asked by Harshit, each of them is described by one integer Q[i] which Harshit wanted him to search in the array. For each query, if he founds it, he had to shout the index of the number, otherwise, he had to shout -1.

##### Input Format:
``````The first line of input contains the size of the array: N

The second line contains N single space-separated integers: A[i].

The third line of input contains the number of queries: Q

The next Q lines of input contain: the number which Harshit wants Aahad to search: Q[i]
``````
##### Output Format:
``````For each test case, print the index of the number if found, otherwise -1.

Output for every test case will be printed in a separate line.
``````
##### Note:
``````You are not required to explicitly print the expected output, just return it and printing has already been taken care of.
``````
##### Constraints:
``````1 <= N <= 10^6
-10^9 <= A[i] <= 10^9
1 <= Q <= 500
-10^9 <= Q[i] <= 10^9

Time Limit: 1sec
``````
##### Sample Input 1:
``````4
2 5 -3 0
2
5
1
``````
##### Sample Output 1:
``````1
-1
``````
##### Explanation For Sample 1:
``````In the 1st test case, 5 is found at index 1

In the 2nd test case, 1 is not found in the array, hence return -1.
``````
##### Sample Input 2:
``````5
100 -2 6 10 11
2
100
6
``````
##### Sample Output 2:
``````0
2
``````   Console