Friday, May 9, 2014

Find second-largest number in the array in at most n+log2n−2 comparisons.

int* findMax(int *arr, int i, int j, int len)
{
if(i == j)
{
int* comp = new int[len];
comp[0] = 1;
comp[1] = arr[i];
return comp;
}
int *comp1 = findMax(arr, i, i+(j-i)/2, len);
int *comp2 = findMax(arr, 1+i+(j-i)/2, j, len);
if(comp1[1] > comp2[1])
{
int k = comp1[0] + 1;
comp1[0] = k;
comp1[k] = comp2[1];
delete [] comp2;
return comp1;
}
else
{
int k = comp2[0] + 1;
comp2[0] = k;
comp2[k] = comp1[1];
delete [] comp1;
return comp2;
}
}

int findSecondMax(int *arr, int len)
{
int *compared =  findMax(arr, 0, len-1, len);
int *max2Arr = findMax(compared, 2, compared[0], compared[0] + 1);
int max2 = max2Arr[1];
delete [] max2Arr;
return max2;
}

No comments:

Post a Comment