Jul 12, 2013

Find minimum element in rotated and sorted array , if elements are not unique

Problem :  For a given array where duplicate elements are present , we have to find minimum element in rotated and sorted array. Part I here(Non-duplicate condition here).
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));  
       }  
 }  
Sample output : 0
-----------------------------------------------------------------------------------------------
Location: Coimbatore, Tamil Nadu, India