find minimum in an rotated sorted array with duplicate entries

25 Views Asked by At

The problem is to find the index of minimum element in an sorted array which is rotated about some pivot. The elements of array may or may not be same.

I tried considering the minimum element as pivot element(the element which belongs at 0 index in original sorted array).

eg.   [40, 50, 60, 10, 20, 30]  
index   0   1   2   3   4   5  

pivot is index 3 as by draggin pivot to first position we can make array sorted again.

my code:

int findMin(int arr[], int low, int high){
int mid = low + (high - low) / 2;

if(low == mid){
    int ans = arr[low] <= arr[high] ? low : high;
    return ans;
}
else if(arr[mid] <= arr[high]) return findMin(arr, low, mid);
else return findMin(arr, mid+1, high);
}

if element at mid <= element at high then pivot might be mid or pivot might be in left of mid

if element at mid > element at high then pivot is definitely on right of mid

problem:

   testcase - [30, 30, 10, 30] output is index 0 but it should be 2  
         index 0  1  2  3
0

There are 0 best solutions below