To Find the minimum element in an array which is sorted and Rotated

Question

I recently faced a programming problem which is as follows:

A sorted array is given and the array is rotated at some unknown point, I have to find the minimum element in it. The Array can contain duplicates too.

For eg:

 Input: {5, 6, 1, 2, 3, 4}

 Output: 1  

 Input: {2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2}   

 Output: 0

I followed simple solution is to traverse trough the complete array and find minimum. This solution requires time O(n).I understand the fact that the minimum element is the one whose previous element is greater than it. If there is no such element present, then there is no rotation and first element would be the minimum.

But i was asked for a O(Logn) solution. Is there a way to solve it in in O(Logn) time?

Answer 1

Off the top of my head:

• Note the first entry
• Perform a binary search; at each stage choose the right half if the pivot element is greater than or equal to the stored first element, and the left half if the pivot element is less.

For instance, given {4,5,6,7,1,2,3}:

• Pivot at 7 > 4, reduce to right half {1,2,3}
• Pivot at 2 < 4, reduce to left half 1.
• Considering only one element, answer is 1.

Answer 2

see this : Since it is sorted array. i need to apply binary search to find pivot..

Lowest element will be where array was pivoted.

Call this findpivot(arr,0,n-1);

int findPivot(int arr[], int low, int high)
{
   // base cases
   if (high < low)  return -1;
   if (high == low) return low;

   int mid = (low + high)/2;   /*low + (high - low)/2;*/
   if (mid < high && arr[mid] > arr[mid + 1])
     return mid;
   if (mid > low && arr[mid] < arr[mid - 1])
     return (mid-1);
   if (arr[low] >= arr[mid])
     return findPivot(arr, low, mid-1);
   else
     return findPivot(arr, mid + 1, high);
}