Last Updated: 9 Jan, 2021

Search In Rotated Sorted Array

Easy

Asked in companies

Solve now

Problem statement

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.

Example:

Input: 'arr' = [12, 15, 18, 2, 4] , 'k' = 2

Output: 3

Explanation:
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).

Input Format

In the first line, two single-space separated integers ‘n’ and ‘k’, respectively.
The second line, ‘n’ single space-separated integers, denotes the array/list 'arr' elements.

Output Format :

The only line contains the index at which 'k' is present in 'arr'.

Note:

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

Solve now

Approaches

01 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.

Solve now

02 Approach

The key observation here is that after rotating ‘arr’, it is divided into two sorted parts/arrays, one from 0 to pivot - 1 and another from pivot to ‘n’ - 1.

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

Here is the algorithm:

We initialize two integer variables, ‘si’ and ‘ei’, denoting the start and end indexes to 0 and ‘n’ -1, respectively. We also initialize 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 where the element ‘k’ may lie. If ‘k’ is present, we return its index. Else, we return -1.

Solve now