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

        // If we stepped into the "larger" subarray, we came too far, 
        // hence search the right subpart    
        if (a[left]  
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.

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;

}
 

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

        // If we stepped into the "larger" subarray, we came too far, 
        // hence search the right subpart    
        if (a[left]  
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.

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

        // If we stepped into the "larger" subarray, we came too far, 
        // hence search the right subpart    
        if (a[left]  
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.