Find the Rotation Count in a Rotated Sorted array
Given an array of distinct numbers sorted in ascending order. The array has been rotated k-times (clockwise) around a pivot, find the value of k.
Example 1:
Input: a = [5, 7, 9, 1, 3]
Output: 3
Explanation: The original array must be [1, 3, 5, 7, 9] and it was rotated 3 times.Example 2:
Input: a = [4, 6, 8, 10, 0, 1, 2]
Output: 4
Explanation: The original array would be [0, 1, 2, 4, 6, 8, 10] and it was rotated 4 times.Example 3:
Input: nums = [5, 10, 15, 20]
Output: 0
Explanation: The array has not been rotated. Binary Search to Find the Rotation Count in a Rotated Sorted array
This problem is exactly similar to the problem Find the Minimum element in a Rotated Sorted Array.
If you analyze the examples carefully, you will notice that the number of rotations is equal to the index of the minimum element (pivot element).
The implementation is exactly same as the implementation of Finding the Minimum element in a Rotated Sorted Array except that in this case we return the index of the minimum element instead of the minimum element itself:
import java.util.Scanner;
public class RotationCountRotatedSortedArray {
private static int findRotationCount(int[] a) {
int n = a.length;
int start = 0;
int end = n - 1;
while(start <= end) {
int mid = (start + end) / 2;
// If the middle element is smaller than its previous element, then it is the minimum element
if(mid > 0 && a[mid] < a[mid-1]) {
return mid;
}
// If the middle is greater than its next element, then the next element is the minimum element
if(mid < n-1 && a[mid] > a[mid+1]) {
return mid+1;
}
if(a[start] <= a[mid]) { // left array is sorted. So the pivot (min element) is on the right side
start = mid+1;
} else { //right array is sorted. So the pivot (min element) is on the left side
end = mid-1;
}
}
return 0; // the array has not been rotated
}
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) {
a[i] = keyboard.nextInt();
}
keyboard.close();
System.out.printf("Rotation Count = %d%n", findRotationCount(a));
}
}