Problem : Find the minimum element in the rotated sorted array.
For example we have array as – 1,3,6,9,12,15.
Now suppose the array is rotated k times ( we don’t know k), such that array becomes
12,15,1,3,6,9
Solution – The answer to this lies on the fact that if we can find the point on inflection and things will be simple. So if we can have 2 sub arrays A and B. We know the array is sorted, so we should take advantage of that fact.
#include <stdio.h> #include <stdlib.h> /* Function to print pair of elements having minimum sum */ int findMin(int *a, int start, int end){ int mid = (start + end)/2; if(start == mid) { return a[mid+1]; } else if(a[start] > a[mid]) { return findMin(a, start, mid); } else if(a[mid+1] > a[start]) { return findMin(a, mid+1, end); } } /* Main program to test above function */ int main() { int arr[] = {-2,-1,12,15,30,-45,-20}; printf("%d",findMin(arr, 0, 6)); getchar(); return 0; }
Time Complexity: O(Log N)
Space Complexity: O(1)
Pingback: Find the Rotation Count in Rotated Sorted array
WRONG: arr={2,4}
findMin(arr, 0, 1)) //returns 4, should return 2
def findMin(array, start, end):
if start == end:
return array[start]
while start < end:
mid = int((start + end) / 2)
if start == mid or end == mid:
break
elif array[start] array[start]:
end = mid
elif array[end] < array[start] and array[mid] array[end]:
return array[end]
else:
return array[start]
if(midarr[mid+1])
return a[mid+1];
if(mid>low && arr[mid]<arr[mid-1])
return a[mid];
if(arr[mid]<arr[high])
return findMin(arr,low,mid-1);
return findMin(arr,mid+1,high);