Question

Let A be an integer array of length n.

Design a divide and conquer algorithm (description and pseudo code) to find the index of an element of the minimum value in the array.

If there are several such elements, your algorithm must return the index of the rightmost element.

For instance, if A = {0,2,4,5,2,0,3,10}, then the algorithm should return 5, which is the index of the second 0.

Answer 1

Pseudo Code ==>

index( arr[ ], n)

{

min = arr[0];

for(int i=0;i<n;i++)

{

if(min>arr[i])

{

min=arr[i];

}

}

for( int i=n-1;i>=0;i--)

{

if(arr[i]==min)

{

return i;

}

}

}

main()

{

arr[ ];

size = sizeof(arr)/sizeof(arr[0]);

minIndex = index(arr,size);

print “ Index is “ ,minIndex;

}

C++ CODE for THIS ===>

#include <iostream>

using namespace std;
int index(int arr[],int n)
{

int min = arr[0];

for(int i=0;i<n;i++)
{
if(min>arr[i])
{
min=arr[i];
}
}

for( int i=n-1;i>=0;i--)
{
if(arr[i]==min)
{
return i;
}
}

}
int main()
{
int arr[]= {0,2,4,5,2,0,3,10};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"Index of the rightmost minimum element : "<<index(arr,size)<<endl;
return 0;
}

OUTPUT SCREENSHOT ===>