Last Updated: 19 Nov, 2020

Rotated sorted array search

Easy

Asked in company

Solve now

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.

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

The basic idea of this approach is to do the modified binary search.

If the given array is sorted, we might do the binary search and can optimise our solution. But since it is rotated by an unknown value, the resulting array is no longer sorted.

We can observe the rotated array can be partitioned precisely into two fully sorted subarrays around a pivot index.

For instance, for the given array [6, 8, 9, 11, 15, 2, 3], the pivot point is an index 5(0th based indexing) and two sub-arrays are [6, 8, 9, 11, 15] and [2, 3]. Notice that each array is indeed fully sorted(in ascending order).

Now, our task is dependent on finding the pivot index. So how do we choose a pivot point?

Note that ith index is the pivot point if and only if ARR[i-1] > ARR[i] and there could be maximum only one such point since all the values of the array are distinct and the array was rotated to the left.

Now to find the pivot point, we could quickly scan the array linearly until we find an index that meets the condition for the pivot index. However, a more efficient way will be to use a modified version of the binary search. Steps are as follows:

Do a modified version of the binary search to find the pivot.
- Initialise the “low” and “high” to 0 and ‘N’ - 1, respectively.
- Iterate until our “low” is less than or equal to “high”
  - Assign (“low” + “high” + 1)/2 to “mid”.
  - Check whether the ARR[“mid”] is smaller than its left neighbour or we have reached to the first element(0th index). If it is, then we have found our pivot index (i.e. “mid”)
  - Otherwise, we will determine what half of the array we need to focus (i.e. in which half the pivot is present). If the ARR[“mid”] is greater than the first element of the array, then pivot will not be present in the first half. Therefore, we will change the search space to [“mid” + 1, “high”]. Else the pivot element must be present in the second half, so change the search space to [“low”, “mid” - 1].
- If the pivot index is not found, then the array will be sorted. Therefore, return 0.
Once we have found the pivot index, we can partition the array into two sorted sub-arrays. Now we will apply a binary search to find the ‘X’ in the relevant sub-array, i.e. the sub-array in which ‘X’ could exist.
Return the index of the element ‘X’ if it is found otherwise return -1.

Solve now

03 Approach

The basic idea of this approach is to find the index of ‘X’ in a single pass of binary search instead of doing it as suggested in approach-2.

We will do the modified version of binary search in a single pass to get the index of ‘X’ if it exists.

Initialise the “low” and “high” to 0 and ‘N’ - 1, respectively and iterate until “low” is less than or equal to “high”.
Assign “mid” = (“low” + “high” + 1)/2
If the element at the index “mid” is ‘X’ then we got the index of our target so return “mid”
Now, we have two sub-arrays left (ARR(“low”, “mid” -1)) and right (ARR(“mid” + 1, “high”)). Note that one of them must be necessarily sorted. Why? Because there can be maximum only one pivot point because all the values of the array are distinct and the array was rotated to the left.
Check if the left sub-array is sorted i.e. ARR[low] < ARR[mid-1].
- Check if ‘X’ can be present in the left sub-array or not. Therefore, if (‘X’ >= ARR[low] && ‘X’ <= ARR[mid-1]) holds true, change the search space to the left part of the array/list i.e. assign “mid” - 1 to “high”.
- Otherwise, ‘X’ would be present (if it exists) in the right sub-array. Change the search space to the right part of the array/list i.e. assign “mid” + 1 to “low”.
Otherwise,
- Check if ‘X’ could be present in the right sub-array or not. Therefore, if (‘X’ >= ARR[mid+1]] && ‘X’ <= ARR[high]) holds true, change the search space to the right part of the array/list i.e. assign “mid” + 1 to “low”.
- Otherwise, ‘X’ would be present (if it exists) in the left sub-array. Change the search space to the left part of the array/list i.e. assign “mid” - 1 to “high”.

Solve now