Search In Rotated Sorted Array
You have been given a sorted array/list ARR consisting of ‘N’ elements. You are also given an integer ‘K’.

Now the array is rotated at some pivot point unknown to you. For example, if ARR = [ 1, 3, 5, 7, 8]. Then after rotating ARR at index 3, the array will be ARR = [7, 8, 1, 3, 5].

Now, your task is to find the index at which ‘K’ is present in ARR.

Note :

1. If ‘K’ is not present in ARR then print -1. 2. There are no duplicate elements present in ARR. 3. ARR can be rotated only in the right direction.

For example, if ARR = [12, 15, 18, 2, 4] and K = 2, then the position at which K is present in the array is 3 (0-indexed).

Follow Up

Can you do this in Logarithmic time and constant additional space?

Input Format

The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow. The first line of each test case contains two single-space separated integers ‘N’ and ‘K’, respectively. The second line of each test case contains ‘N’ single space-separated integers, denoting the elements of the array/list ARR.

Output Format :

For each test case return the index at which K is present in ARR.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Search In Rotated Sorted Array

You have been given a sorted array/list ARR consisting of ‘N’ elements. You are also given an integer ‘K’.

Now the array is rotated at some pivot point unknown to you. For example, if ARR = [ 1, 3, 5, 7, 8]. Then after rotating ARR at index 3, the array will be ARR = [7, 8, 1, 3, 5].

Now, your task is to find the index at which ‘K’ is present in ARR.

Note :

1. If ‘K’ is not present in ARR then print -1.
2. There are no duplicate elements present in ARR. 
3. ARR can be rotated only in the right direction.

For example, if ARR = [12, 15, 18, 2, 4] and K = 2, then the position at which K is present in the array is 3 (0-indexed).

Follow Up

Can you do this in Logarithmic time and constant additional space?

Input Format

The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains two single-space separated integers ‘N’ and ‘K’, respectively.

The second line of each test case contains ‘N’ single space-separated integers, denoting the elements of the array/list ARR.

Output Format :

For each test case return the index at which K is present in ARR.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 5000
0 <= K <= 10^5
0 <= ARR[i] <= 10^5

Time Limit : 1 second

Accepted Answer

This question could be solved using Binary search which would have a time complexity of O(log n). The approach would be:
1. Find the mid = (low + high)/2
2. If key is present at middle point, return mid.
3. If arr[low….mid] is sorted
a) If key to be searched lies in range from arr[low] to arr[mid], apply binary search for arr[low..mid].
b) Else apply for arr[mid+1..high]
4. Else (arr[mid+1..high] must be sorted)
a) If key to be searched lies in range from arr[mid+1]
to arr[high], apply binary search for arr[mid+1..high].
b) Else recur for arr[low..mid]

Accepted Answer

Naive Approach

Naively traverse the array and find if ‘K’ is present in ARR or not. If ‘K’ is present in ARR return its index else return -1.

Space Complexity: O(1)Explanation:

O(1), i.e. constant space complexity.

Time Complexity: O(n)Explanation:

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

We are iterating over the array/list ARR once. Hence, the time complexity is O(N).

Java (SE 1.8)

/*

    Time Complexity : O(N)

    Space Complexity : O(1)



    where N is the length of array.

*/



import java.util.ArrayList;



public class Solution {

    public static int findPosition(ArrayList arr, int n, int k) {

        int pos = -1;

        // Finding the element using linear search.

        for (int i = 0; i < n; i++) {

            if (arr.get(i) == k) {

                pos = i;

            }

        }



        return pos;



    }



}

Python (3.5)

'''

    Time Complexity : O(N)

    Space Complexity : O(1)



    where N is the length of array.

'''





def findPosition(arr, n, k):



    pos = -1



    for i in range(n):

   

        if(arr[i] == k):

            pos = i



    return pos

C++ (g++ 5.4)

/*

    Time Complexity : O(N)

    Space Complexity : O(1)



    where N is the length of array.

*/





int findPosition(vector& arr, int n, int k)

{

    int pos = -1;



    for(int i = 0; i < n; i++)

    {

        if(arr[i] == k)

        {

            pos = i;

        }

    }



    return pos;

}

Accepted Answer

Binary Search

The key observation here is that after rotating ARR, it is divided into two sorted parts/arrays, one from 0 to pivot - 1 another from pivot to N - 1.

Now the problem boils down to finding the pivot point. So, we will modify the binary search algorithm and first find the pivot point in ARR.

Here is the algorithm:

We initialise two integer variables ‘si’ and ‘ei’ denoting the start index and the end index to 0 and N -1, respectively. We also initialise another integer variable ‘pivot’ to 0 that stores the index of the pivot element.

In the modified binary search, we will compare ARR[mid] with ARR[0] because if ARR[mid] < ARR[0], then it is guaranteed that ‘pivot’ is mid or present on its left side. Else, ‘pivot’ is present on the right side.

The modified binary search to find the pivot point:

We find the index of the middle element of ARR as mid = si + (ei - si) /2 .
If (ARR[mid] < ARR[0])
1. pivot = mid
2. We update the end index ei, ei = mid - 1.
Else
1. We update the start index si, si = mid + 1.

After finding the pivot, we can easily locate the two sorted parts of ARR, one starting from 0 to pivot - 1 and the other from pivot to N - 1. Now, we apply binary search in that sorted part of ARR in which the element K may lie. If K is present, we return its index. Else, we return -1.