Rotation Point in Sorted Rotated Array

Question : What is the optimal algorithm to find the minimum element given a rotated sorted array of integers? A rotated sorted array of integers is the output array of a rotation operation performed on a sorted array. Eg:  3 5 6 1 2

Answer : One way to solve the above problem in linear time is to get the minima from the array using difference array and then finding the sign change from positive to negative.This will solve the problem in O(n) time.

/*
* Solution for O(n) time complexity
*/
int getRotationPoint(int *arr,int length)
{
    int *diff=(int *)malloc(sizeof(int)*length-1);
    if(length==1)
    return 0;
    assert(length>=2);
    for(int i=1;i0)?PS:NG;
    for(int i=0;i0)?PS:NG;
        if((sg==NG)&&(sign==PS))
        {
            index=i;
            break;
        }
        sign=sg;
    }
    return index+1;
}

However for an even tighter bound we modify the binary search algorithm and use it.We also could use the fact that for a sorted array, if the array were circular the index of the smallest would be the index after the largest element.Hence this solution is a O(log n) solution.

/*
* Solution for O(nlogn) time
*/
int getRotationPointBi(int *arr,int length)
{
    int first=0;
    int last=length-1;
    int middle=(last+first)/2;
    while(last>first)
    {
        middle=(last+first)/2;
        if(arr[first]>=arr[middle])
        last=middle;
        else if(arr[middle]>=arr[last])
        first=middle;
    }
    return middle+1;
}