Question: You are given an array of N integers. Your job is to find maximum and second maximum element in N+logN comparisons.

Solution: #include
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);
}