Question
Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?Would this affect the run-time complexity? How and why?
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
The array may contain duplicates.
Array Binary Search about/Solution
This question is simply a modified version of previous question. The special cases of the input makes it O(n) worst case complexity.
My Code
public class Solution {
public int findMin(int[] num) {
if (num == null || num.length == 0) {
return 0;
}
return helper(num, 0, num.length - 1);
}
private int helper(int[] num, int left, int right) {
if (num[left] < num[right] || left == right) {
return num[left];
} else if (num[left] == num[right]) {
return helper(num, left + 1, right);
} else if (left + 1 == right) {
return num[right];
}
int mid = left + (right - left) / 2;
if (num[mid] >= num[left]) {
return helper(num, mid, right);
} else {
return helper(num, left, mid);
}
}
}