# 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;
// 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
-----------------------------------------------------------------------------------------------