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 was a pretty standard Binary Search Question and I had solved this question before on platforms like LeetCode and CodeStudio . I was asked this question to test my implementation skills and how well do I handle Edge Cases .

Approach :
1) The idea is to find the pivot point, divide the array in two sub-arrays and perform binary search.
2) The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only element for which next element to it is smaller than it.
3) Using the above statement and binary search pivot can be found.
4) After the pivot is found out divide the array in two sub-arrays.
5) Now the individual sub – arrays are sorted so the element can be searched using Binary Search.

TC : O(Log(N))
SC : O(1)

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.