26 Dec 2011

```
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 2 ^{2 comparisons (4 groups)
.
The (m-2)-st level it takes 2 x 2}(m-2)* comparison (2

To sum it up, 2 + 2^{2 + 2}3 + … + 2^{(m-1) + 2}(m-1) comparisons
That is 2^{m - 1 - 1 + 2}(m-1).

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