Duplicates cannot be handled in O(n) since it cannot be decided whether to left half or right half by doing constant number of comparisons at the middle.
For example : array sample : {2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2} .
Since middle elements and start/end are same so we cannot decide whether go left or right.
So we have to check in both direction which side contain lower value.
if (arr@lowIndex == arr@midIndex&& arr@highIndex == arr@midIndex)
//return minimum of result obtained from both side.
return min(findMinConsideringDuplicates(arr, low, mid-1),
findMinConsideringDuplicates (arr, mid+1, high)); It causes O(Logn ) degenerate to O(n) if duplicates are found in array.
Sample code in java can be written as :
public class FindMinimumInRotatedArrayWithDuplicates {
public FindMinimumInRotatedArrayWithDuplicates() {
super();
}
int findMinConsideringDuplicates(int arr[], int low, int high)
{
// It is needed to handle the case when array is not
// rotated at all
if (high < low) return arr[0];
// If there is only one element left
if (high == low) return arr[low];
// Find mid
int mid = low + (high - low)/2; /*(low + high)/2;*/
// Check if element (mid+1) is minimum element. Consider
// the cases like {1, 1, 0, 1}
if (mid < high && arr[mid+1] < arr[mid])
return arr[mid+1];
// This case causes O(n) time
if (arr[low] == arr[mid] && arr[high] == arr[mid])
return Math.min(findMinConsideringDuplicates(arr, low, mid-1), findMinConsideringDuplicates(arr, mid+1, high));
// Check if mid itself is minimum element
if (mid > low && arr[mid] < arr[mid - 1])
return arr[mid];
// decide go to left half or right half
if (arr[high] > arr[mid])
return findMinConsideringDuplicates(arr, low, mid-1);
return findMinConsideringDuplicates(arr, mid+1, high);
}
public static void main(String[] args) {
FindMinimumInRotatedArrayWithDuplicates findMinimumInRotatedArraywirhDup =
new FindMinimumInRotatedArrayWithDuplicates();
int[] arr = {2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2};
System.out.println(findMinimumInRotatedArraywirhDup.findMinConsideringDuplicates(arr, 0, 11));
}
} -----------------------------------------------------------------------------------------------
