For example the array [4, 5, 1, 2, 3] is (right) rotated twice.
Before proceeding to find a solution, let’s note some observations.
To find the number of rotations, we have to find the smallest element in the array. If we find the index of the smallest element in the array, that will indicate the number of rotations.
In the above example, the smallest number is 1 which is located at index ‘2’. We can easily verify that the array is rotated twice.
A simple approach could be to use a linear search to find the least number and return it’s index. This approach will obviously take O(n) time. Can we perform better than that?
Yes, it can be done by utilizing the sorted property of the array. Here is how we can do this.
Just like Binary search, we can use divide and conquer approach. We write a recursive function which will take the array, lower and upper bound as its parameters.
We first check whether the array is sorted from the beginning (not rotated). This can be done by checking if array[low] <= array[high]. If it is not rotated, we can simply return the index low.
Next we check if the middle element is the smallest element by comparing it with the previous and next elements.
If this condition is satisfied, then we return mid. One caution while calculating the next and previous indices is to consider the array boundaries. We have to assume that the array is circular.
//if mid is at 0, consider last element as previous
int prev = (mid – 1 + len) % len;
//if mid is the last element, consider next element as the first
int next = (mid + 1) % len;
Next, we check which portion is already sorted. If the left portion is properly sorted (without rotations), we search in the right half. Otherwise we search in the left half.
return findRotations(arr, mid+1, high);
else
return findRotations(arr, low, mid-1);
Even more simplified version of the algorithm is given below.
int findRotationCount(const vector<int>& arr)
{
int low = 0, high = arr.size() - 1;
while( arr[low] > arr[high] )
{
int mid = low + (high - low)/2;
if( arr[mid] > arr[high] )
low = mid + 1;
else
high = mid;
}
return low;
}
int findRotateCount(const vector<int>& arr, int low, int high)
{
if( arr[low] > arr[high] )
{
int mid = low + (high-low)/2;
if( arr[mid] > arr[high] )
return findRotateCount( arr, mid+1, high);
else
return findRotateCount( arr, low, mid);
}
else
return low;
}