I have seen many variants of problems where given array is sorted but it is rotated K time. Rotation here means last element of array becomes first and first is moved to second, second to third and second last element to last position. This is K=1 rotation. Fro K=2, same procedure is repeated. Look at this example.
|Normal sorted array
|Rotated sorted array
There are some problems which are based on this which are generally asked during telephonic or online coding rounds. Below is the list:
1. Given a sorted array, rotated K times (K not known), Find K or pivot at which it is rotated.
Same question can be paraphrase to ask for minimum element in such an array.
2. Given an sorted array rotated K times (K not known), find an element in it.
3. Rotate an array K times (Finally K known)!
Let’s analyse and see solution for each of above problem.
Problem 1: Find minimum element or find K for which array is rotated.
There is simple brute force algorithm with O(N) complexity, that is to scan through array and check for each element for following condition.
Element which satisfy above condition, is our required element.
Now question is can we do better?
Idea here is that all the elements on the right side of pivot or minimum element will be greater than it.
We randomly pick any element and check if all elements on the right side are greater. We don’t need to go through each element, compare it with the last element, if last is greater, we are good. (Remember we are working sorted array).
It is necessary condition but is this sufficient condition?
No, as any number after pivot will satisfy that condition. What is unique to pivot then? It is that element just before pivot is greater than pivot. Combine these conditions and we can find our pivot.
How can we select the element. Well, just take the middle element and if first condition is satisfied and second not, we look in lower part of the array.
If first condition is not satisfied, we look in the upper part of the array.
Complexity of above code is O(log N).
Problem 2: Find an element in a sorted rotated array
Again brute force algorithm gives us O(N) complexity solution. Can we do better? Can binary search algorithm be applied here?
How to eliminate sub arrays?
If mid is equal to element we are looking for, return mid.
If not, what are the cases?
Case 1 : If the lower half of the array is sorted.
(check if A[mid] >= A[start])
Check if the element being looked for is greater than A[start]
and less than A[mid]
discard the upper array we have to look in lower array.
Else look in upper sub array.
Case 2 : If lower array is not sorted.
If element is greater than A[mid] && less than A[end], look in
upper sub array.
else look in lower sub array.