Finding the minimum in a sorted, rotated array

Given an array that is first sorted non-decreasing and then rotated
right by an unspecified number of times, find the index of its minimal
element efficiently. If multiple such minimal elements exist, return
the index of any one.


Idea: Conceptually, divide the array into two parts: the "larger"
subpart (to the left) which consists of large numbers brought here
from the extreme right by rotation, and the "smaller" subpart which
starts with the smallest element. We can always tell in which part we
are, and move left/right accordingly.

Notes: When the array has multiple minimal elements, the index of the leftmost one in the "right" subpart is returned.

int getMinimIndex (const int *const a, size_t left, size_t right)
{
        assert(left> 1;

        // If we stepped into the "larger" subarray, we came too far, 
        // hence search the right subpart    
        if (a[left] <= a[mid] )
                return getMinimIndex(a, mid, right);
        else
        // We're still in the "smaller" subarray, hence search left subpart
                return getMinimIndex(a,left, mid);
}

Unit tests:

\#define lastIndex(a)  ((sizeof(a)/sizeof(a[0]))-1)

int main()
{
        int a1[] = {7,8,9,10,11,3};
        int a2[] = {1};
        int a3[] = {2,3,1};
        int a4[] = {2,1};
        int a5[] = {2,2,2,2,2};
        int a6[] = {6,7,7,7,8,8,6,6,6};
        int a7[] = {1,2,3,4};

        printf("\n%d", getMinimIndex(a1,0, lastIndex(a1))); // 5
        printf("\n%d", getMinimIndex(a2,0, lastIndex(a2))); // 0
        printf("\n%d", getMinimIndex(a3,0, lastIndex(a3))); // 2
        printf("\n%d", getMinimIndex(a4,0, lastIndex(a4))); // 1
        printf("\n%d", getMinimIndex(a5,0, lastIndex(a5))); // 3 
        printf("\n%d", getMinimIndex(a6,0, lastIndex(a6))); // 6
        printf("\n%d", getMinimIndex(a7,0, lastIndex(a7))); // 0

        return 0;

}

The algorithm does not work correctly.

It fails on the following:

int a1[] = {10,1,10,10,10,10,10};

printf("\n%d", getMinimIndex(a1,0, lastIndex(a1))); // 5

It prints 5 instead of 1.

The problem is in case the elements can repeat, you assumption that we can recurse on the left or right half is wrong.

In fact, if elements can repeat, any algorithm will be in the worst case Omega(n), while yours is always O(logn), so it is incorrect.

StackExchange Code Review Q#1514, answer score: 7