Find Minimum Element in Rotated Sorted Array
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array a = [0, 1, 2, 4, 6, 8, 10] might become:
[8, 10, 0, 1, 2, 4, 6]if it was rotated 2 times.[4, 6, 8, 10, 0, 1, 2]if it was rotated 4 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given that the sorted array is guaranteed to have unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time complexity.
Example 1:
Input: nums = [5, 7, 9, 1, 3]
Output: 1
Explanation: The original array was [1, 3, 5, 7, 9] rotated 3 times.Example 2:
Input: nums = [4, 6, 8, 10, 0, 1, 2]
Output: 0
Explanation: The original array was [0, 1, 2, 4, 6, 8, 10] and it was rotated 4 times.Example 3:
Input: nums = [5, 10, 15, 20]
Output: 5
Explanation: The original array was [15, 10, 15, 20] and it was rotated 4 times. Find the Minimum element in Rotated Sorted Array
This problem is a variation of the problem Search an element in a Rotated Sorted Array.
If you analyze the examples closely, you will notice that the minimum element is the only element in the given rotated sorted array that is smaller than its previous element.
The minimum element is also the pivot element. The subarray on the left of the pivot and on the right of the pivot are sorted.
We will use this property to find the minimum element using binary search:
import java.util.Scanner;
public class FindMinimumElementInRotatedSortedArray {
private static int findMinimumElement(int[] a) {
int n = a.length;
int start = 0;
int end = n - 1;
// If the first element is less than the last element then there is no rotation. The first element is minimum.
if(a[start] <= a[end]) {
return a[start];
}
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 a[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 a[mid+1];
}
if(a[start] <= a[mid]) { // left array is sorted. So the pivot is on the right side
start = mid+1;
} else { //right array is sorted. So the pivot is on the left side
end = mid-1;
}
}
return -1;
}
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("Minimum Element = %d%n", findMinimumElement(a));
}
}# Output
$ javac FindMinimumElementInRotatedSortedArray.java
# Example 1
$ java FindMinimumElementInRotatedSortedArray
7
0 1 2 4 6 8 10
Minimum Element = 0
# Example 2
$ java FindMinimumElementInRotatedSortedArray
7
4 6 8 10 0 1 2
Minimum Element = 0
# Example 3
$ java FindMinimumElementInRotatedSortedArray
7
1 2 4 6 8 10 0
Minimum Element = 0
# Example 4
$ java FindMinimumElementInRotatedSortedArray
7
2 4 6 8 10 0 1
Minimum Element = 0
# Example 5
$ java FindMinimumElementInRotatedSortedArray
7
10 0 1 2 4 6 8
Minimum Element = 0