Find the Minimum Element in the Rotated Sorted array

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)

4 Thoughts on “Find the Minimum Element in the Rotated Sorted array

  1. Pingback: Find the Rotation Count in Rotated Sorted array

  2. sidhartha on November 17, 2013 at 9:23 am said:

    WRONG: arr={2,4}
    findMin(arr, 0, 1)) //returns 4, should return 2

  3. sid_Python on November 17, 2013 at 12:49 pm said:

    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]

  4. Manan Shah on February 23, 2015 at 9:43 pm said:

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

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation