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.