Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 9 Jan, 2021

Easy

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

```
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).
```

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

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

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

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.

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
*mid = si + (ei - si) /2.* - If (arr
*[mid] < arr[0]*)*pivot = mid**We update the end index ei, ei = mid - 1.*

- Else
- We update the start index
*si, si = mid + 1*.

- We update the start index

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.

Similar problems