# Search In Rotated Sorted Array

Posted: 21 Jul, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### Note:

``````Can you solve each query in O(logN) ?
``````
##### 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
`````` Approach 1

The idea here is to do a linear approach which apparently is a brute force way to do this.

• Visit every element one by one.
• Check if the current element that you are looking at is the key value that needs to be searched. If the element is found, return the index at which you find it.
• Once all the elements are visited and you don't find the key-value, return -1.