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