Min and Max

26 Dec 2011

Min and Max

Given an array, find Min and Max with the least comparison.

Now the classic way to do is to loop. That's 2n comparisons on the worse case. The best case is using n comparisons.

This kind of problem is somewhat classic. The technique that hits my mind is divide-and-conquer.

Let's try divide them into 2 groups.

We find Max and Min on each group; let's say it take k comparisons. Now to find the global Max and Min, it takes 2 comparisons.

The smallest group consists of 2 elements. It takes only 1 comparison to find both Min and Max.

Let's analyze it. First, assume that n = 2^m for the sake of simplicity.

This means that at the 1st level it takes 2 comparisons. The 2nd level it takes 4 comparisons (2 groups). The 3rd level it takes 2 x 22 comparisons (4 groups) . The (m-2)-st level it takes 2 x 2(m-2) comparison (2(m-2) groups). The (m-1)-st level, it takes *2(m-1)* comparison (2^(m-1) groups).

To sum it up, 2 + 22 + 23 + … + 2(m-1) + 2(m-1) comparisons That is 2m - 1 - 1 + 2(m-1).

That is a little bit less than (n + 1/2n) comparisons, which is the wanted number.