Problem Statement
Given an array of numbers which is sorted in ascending order and also rotated by some arbitrary number, find if a given ‘key’ is present in it.
Write a function to return the index of the ‘key’ in the rotated array. If the ‘key’ is not present, return -1. You can assume that the given array does not have any duplicates.
Note: You need to solve the problem in O(logn) time complexity.
Example 1:
Input: [10, 15, 1, 3, 8], key = 15
Output: 1
Explanation: '15' is present in the array at index '1'.
Example 2:
Input: [4, 5, 7, 9, 10, -1, 2], key = 10
Output: 4
Explanation: '10' is present in the array at index '4'.
Constraints:
1 <= arr.length <= 5000- -10<sup>4</sup> <= arr[i] <= 10<sup>4</sup>
- All values of nums are unique.
- arr is an ascending array that is possibly rotated.
- -10<sup>4</sup> <= key <= 10<sup>4</sup>
Why this is a Modified Binary Search problem
| What the question says | The signal it matches |
|---|---|
| "sorted in ascending order and also rotated by some arbitrary number" | the input is sorted in a way that has been rotated |
| "You need to solve the problem" | the expected complexity is stated as logarithmic |
This is the sorted, then rotated variant: one half is always properly sorted, so decide which half that is.
The closest alternative. Find the rotation point first, which is the next problem, then run a normal binary search on whichever half can hold the key. Two logarithmic passes, and it is a perfectly good answer that is easier to explain under pressure.
The one-pass version is what the introduction calls the whole trick. After a rotation at least one half is still in perfect order, and comparing the middle element with the first tells you which. Once you know the sorted half, you can test whether the key lies inside its range. If it does, search there; if not, the key can only be in the other half. Note the statement rules out duplicates, and that guarantee is what makes the comparison reliable.
Solution
The problem follows the Binary Search pattern. We can use a similar approach as discussed in Order-agnostic Binary Search and modify it similar to Search Bitonic Array to search for the ‘key’ in the rotated array.
After calculating the middle, we can compare the numbers at indices start and middle. This will give us two options:
- If
arr[start] <= arr[middle], the numbers fromstarttomiddleare sorted in ascending order. - Else, the numbers from
middle+1to end are sorted in ascending order.
Once we know which part of the array is sorted, it is easy to adjust our ranges. For example, if option-1 is true, we have two choices:
- By comparing the ‘key’ with the numbers at index
startandmiddlewe can easily find out if the ‘key’ lies between indicesstartandmiddle; if it does, we can skip the second part =>end = middle -1. - Else, we can skip the first part =>
start = middle + 1.
Let’s visually see this with the above-mentioned Example-2:
Since there are no duplicates in the given array, it is always easy to skip one part of the array in each iteration. However, if there are duplicates, it is not always possible to know which part is sorted. We will look into this case in the ‘Similar Problems’ section.
Code
Here is what our algorithm will look like:
Time Complexity
Since we are reducing the search range by half at every step, this means that the time complexity of our algorithm will be O(logN) where ‘N’ is the total elements in the given array.
Space Complexity
The algorithm runs in constant space O(1).
Similar Problems
Since we are reducing the search range by half at every step, this means that the time complexity of our algorithm will be O(logN) where ‘N’ is the total elements in the given array.
Problem 1
How do we search in a sorted and rotated array that also has duplicates?
The code above will fail in the following example!
Example 1:
Input: [3, 7, 3, 3, 3], key = 7
Output: 1
Explanation: '7' is present in the array at index '1'.
Solution
The only problematic scenario is when the numbers at indices start, middle, and end are the same, as in this case, we can’t decide which part of the array is sorted. In such a case, the best we can do is to skip one number from both ends: start = start + 1 & end = end - 1
Code
The code is quite similar to the above solution:
Time Complexity
This algorithm will run most of the times in O(logN) . However, since we only skip two numbers in case of duplicates instead of half of the numbers, the worst case time complexity will become O(N).
Space Complexity
The algorithm runs in constant space O(1).