Finding Minimum Element In sorted Rotated Array

In Today's Post we will discuss a program whose objective is to find a minimum element in an array but what's the fun in doing that.... so the twist is that the array is rotated.

Approach:

The Approach is similar to binary search with some extra conditions to check whether the array is left rotated, right rotated or not rotated at all.

the above mentioned things can be done in O(log n) time but for handling duplicates an extra condition need to be added which extends the time complexity of the program to O(n).

Here's the code:

#include<stdio.h>

int min(int x,int y)

{

 return (x>y)? y : x ;

}

int findmin(int arr[],int low,int high)

{

    if(high<low)

    return arr[0];

    if(low==high)

        return arr[low];

    int mid=low+(high-low)/2;

    if(mid<high && arr[mid+1]<arr[mid])

        return arr[mid+1];

    if(arr[mid]==arr[low]&&arr[mid]==arr[high])

        return min(findmin(arr,low,mid-1),findmin(arr,mid+1,high));

    if(low<mid && arr[mid-1]>arr[mid])

        return arr[mid];

    if(arr[mid]<arr[high])

        return findmin(arr,low,mid-1);

    return findmin(arr,mid+1,high);

}

int main()

{

    int arr[] =  {3, 3, 3, 4, 4, 4, 4, 5, 3, 3};

    int n=sizeof(arr)/sizeof(arr[0]);

    int k=findmin(arr,0,n-1);

    printf("%d",k);

    return 0;

}

Do comment.. :)

Viva La Raza

Sid