Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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:

 

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

}

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

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

}

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

share|improve this question
    
I made a small error here: the return type of the getMinimIndex() should be size_t not int , and the printf formatting should change accordingly to %ud –  Ganesh Mar 29 '11 at 4:22
add comment

3 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
thanks for pointing out the subtle error. But without repetitions it should still work –  Ganesh Mar 31 '11 at 6:15
add comment

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;
    }
}
share|improve this answer
    
True, but I only meant running time complexity by "efficiency" –  Ganesh Mar 29 '11 at 4:10
    
Well, in that case, your algorithm already runs in O(log n), which is the best you can do for searching. –  Adeel Zafar Soomro Mar 29 '11 at 4:20
1  
Actually the algorithm is unsound. See my answer for a failing test case. –  Aryabhata Mar 31 '11 at 1:12
    
@Moron: Hah, serves me right for not writing enough tests. Good catch. –  Adeel Zafar Soomro Mar 31 '11 at 10:57
add comment
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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.