Rotated sorted array search

Easy

0/40

5 upvotes

Asked in company

Problem statement

You have been given an array of ‘N’ distinct integers which is sorted in ascending order and then rotated to the left by an unknown which you don’t know beforehand. For a given integer ‘X’, your task is to find the index of ‘X’ in the given array if it exists.

Please note that the sorted array A : [2, 3, 6, 8, 9, 11, 15] might become [6, 8, 9, 11, 15, 2, 3] after rotating it twice to the left.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain two space-separated integers ‘N’ and ‘X’ where     ‘N’ is the length of the array, and ‘X’ is the integer which is described above.

Output Format:

For each test case, print the index(0th based) of ‘X’ if it exists in the given array else print -1.

Output for every test case will be printed in a separate line.

Note:

You don’t need to print anything; It has already been taken care of.

Constraints:

1 <= T <= 50
1 <= N <= 10000
0 <= X <= 10^5
0 <= ARR[i] <= 10^5

Where ‘T’ is the number of test cases.
Where 'N' is the number of elements in the given array/list and ‘X’ is the integer which you need to search in the array. 
And, ARR[i] denotes the value ith element of the input array.

Time limit: 1 sec

Sample Input 1:

Sample Output 1:

1
-1

Explanation of sample input 1:

In the first test case, the given array is [2, 3, 1]. And 3 is found at index 1 of the array.

In the second test case, the given array is [6, 8, 9, 2, 3]. 4 doesn’t exist in the given array. Therefore, -1 will be the output.

Sample Input 2:

2
7 6
6 8 9 11 15 2 3
4 4
1 2 3 4

Sample Output 2:

0
3

Explanation for sample input 2:

In the first test case, the given array is [6, 8, 9, 11, 15, 2, 3], and 6 is found at index 0 of the array.
In the second test case, the given array is [1, 2, 3, 4], and 4 is found at index 3 of the array.

Hint 1

Hint 2

Hint 3

Can you think of going through each element?

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

The basic idea is to iterate through all the elements of the array and find the position of ‘X’ if it exists in the array. Steps are as follows:

Iterate through ARR
- If the current element is ‘X’ return the index
If ‘X’ is not present in the array, return -1.

Time Complexity

O(N), where ‘N’ is the length of the given array/list.

Since we are iterating through the array/list once, so the overall time complexity will be O(N).

Space Complexity

O(1)

Since we are not using any extra space, the overall space complexity will be O(1).

(100% EXP penalty)

Rotated sorted array search

Console