New update is available. Click here to update.

Topics

You have been given a sorted array/list * 'arr'* consisting of

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

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

Detailed explanation

```
4 3
8 9 4 5
```

```
-1
```

```
For the test case, 3 is not present in the array. Hence the output will be -1.
```

```
4 3
2 3 5 8
```

```
1
```

```
Try to do this in O(log(n)).
```

```
1 <= n <= 10^5
0 <= k <= 10^9
0 <= arr[i] <= 10^9
Time Limit: 1 second
```