Finding the minimum in a sorted, rotated array

Question

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

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;

}

Answer 1

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.

Answer 2

Your algorithm works for sequences that are strictly increasing (as @Moron points out). If efficiency is a consideration, you may wish to employ iteration instead of recursion.

int getMinimIndex (const int *const a, size_t left, size_t right)
{
    while (1)
    {
        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])
            left = mid;
        else
        // We're still in the "smaller" subarray, hence search left subpart
            right = mid;
    }
}

Answer 3

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

In the second line it seems that it can be left = mid + 1. Because we already know that mid is part of larger subarray so we can skip it and search starting from the next item.

Answer 4

Why not just?

int minimumIndex(size_t arrayLength, const int* const array){
    int lowestIndex = 0;
    for(size_t curIndex = 0; curIndex < arrayLength; ++curIndex){
        if(array[curIndex] < array[lowestIndex]){
            lowestIndex = curIndex;
        }
    }
    return lowestIndex;
}

• Runs with O(n) complexity, and unless using really huge arrays and ancient hardware will still be fast enough.
• Even if the entire array is the same value, it will still only ever return the first index.
• It doesn't care whether the array is sorted or not.
• Unless provided with invalid input, it will always work correctly.
• Provably correct even if the numerical type in the array is changed.
• Uses 0 extra memory, 0 pointers.
• Doesn't self recurse, so it will never hit recursion depth limits.
• Only a single function call, since each recursive call requires a new stack frame, a jump, and a ret instruction. Plus any memory allocs/deallocs because of it being a new scope.

If it's just for kicks, Feel free to disregard this answer (I recently implemented Merge Sort "just for kicks" so I think I understand why you wrote it)