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);