Problem of the day
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'.
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.
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
Naively traverse the array and find if ‘k’ is present or not.
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.
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).
O(1), i.e. constant space complexity.