To find maximum and second maximum element in an Array using N+logN comparisons

#include <stdio.h>

typedef struct
{
unsigned a;
unsigned b;
}Max2ndMax;

Max2ndMax findMaxN2ndMax(int a[], int i, int j)
{
Max2ndMax ret;
int n = j - i;

if(n == 0)
{
ret.a = ret.b = a[i];
return ret;
}
else if(n == 1)
{
if(a[i] > a[j])
ret.a = a[i], ret.b = a[j];
else
ret.a = a[j], ret.b = a[i];

return ret;
}

int mid = (i + j)/2;
Max2ndMax ret1 = findMaxN2ndMax(a, i, mid);
Max2ndMax ret2 = findMaxN2ndMax(a, mid + 1, j);

if(ret1.a > ret2.a)
{
ret.a = ret1.a;
ret.b = ret2.a > ret1.b ? ret2.a : ret1.b != ret1.a ? ret1.b : ret2.a;

}
else
{
ret.a = ret2.a;
ret.b = ret1.a > ret2.b ? ret1.a : ret2.b != ret2.a ? ret2.b : ret1.a;
}

return ret;
}


int main()
{
int n;

scanf("%d", &n);

int a[n];

int i;

for(i = 0; i < n; ++i)
scanf("%d", a + i);

Max2ndMax m = findMaxN2ndMax(a, 0, n-1);

printf("Max = %d\t 2ndMax = %d\n", m.a, m.b);
}
Advertisements

4 thoughts on “To find maximum and second maximum element in an Array using N+logN comparisons

  1. I have doubt regarding the no. of comparisions ?The recursion will reach the base case when array size becomes 1 or 2.Thus at the bottom most level of recursion tree we make n/2 comparisons(comparing all elements pair wise) , for all other levels we make three comparisons for each pair of "Max2ndMax".Thus total comparisons = n/2+3*( 2^0+2^1…2^(lgn-2) )=2*n-3

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s