Given an array that is first sorted non-decreasing and then rotated right by an unspecified numnber 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. 

Here's my code for review:

<pre> <code>

int getMinimIndex (const int *const a, size_t left, size_t right)
{
        assert(left<= right);

        // Special cases:
        // 1 If left & right are same , return 
        if (left ==right)
                return left;

        // 2 For an array of size 2, return the index of minimal element
        if (left == right - 1)
                return a[left]<=a[right]?left:right;

        // 3 If the array wasn't rotated at all, 
        if (a[left] < a[right])
                return left;


        // General case
        // Go to the middle of the array
        size_t mid = (left + right) >> 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);
}


</pre> </code>


Here's code I wrote to unit-test this:

<pre> <code>
\#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;

}
</pre> </code>


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