Problem title
Difficulty
Avg time to solve

K Largest Element
Moderate
10 mins
Next Permutation
Moderate
15 mins
Moderate
10 mins
Search In Rotated Sorted Array
Moderate
30 mins
Allocate Books
Moderate
10 mins
Ninja’s Training
Moderate
30 mins
Alien dictionary
Hard
46 mins
Frog Jump
Easy
30 mins
Order of People Heights
Ninja
45 mins
N-th Term Of GP
Easy
15 mins
160

# Search In Rotated Sorted Array

Difficulty: MEDIUM
Contributed By
Ashwani |Level 1
Avg. time to solve
30 min
Success Rate
65%

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 <= 10^5
-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 Input 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