How do I find the max and min value of an array in 3n/2−2 comparisons?

Question

So I'm using this method to find the min and max value of an array simultaneously where I split the array into n/2 and n/2 parts. I then keep splitting each part until I have either a pair of numbers or a single number.

What I'm trying to do now is the same thing but I'm trying to come up with a method that will always use 3n/2−2 comparisons. The method above doesn't use 3n/2−2 comparisons each time. So I just want to visualize how this is done on an array before I start to programming the method.

Answer 1

Imagine having a tournament made of the array elements. Group the array elements into pairs, then compare each pair. Put the larger numbers into one group and the smallers number into another group. The maximum value of the original array must be the max of the larger group and the minimum value of the original array must be the min of the smaller group. Initially, you do n/2 comparisons to make the split, and from there you need to find the max and min of two groups of n/2 elements each, which can be done with a total of n/2 - 1 comparisons per group. Overall, this is 3n / 2 - 2 compares.

... assuming, of course, you have an even total number of elements. Think about what happens if that isn't the case.

Answer 2

There is an algorithm for finding minimum and maximum simultaneously (in one pass over an array), requiring $O(1)$ additional memory.

The idea is to process the elements of the input array in pairs as in this answer by templatetypedef, but without explicit grouping, so (almost) no additional memory is needed.

A coarse sketch of the algorithm:

1. Compare the first pair of elements between each other.

2. Compare the smaller element with the current minimum and update the current minimum if needed.

3. Compare the larger element with the current maximum and update the current maximum if needed.

4. Repeat for the rest pairs.

The analysis of the number of comparisons is the same as given by @templatetypedef.

This algorithm is described in detail in "Introduction to Algorithms", 3ed by Cormen, Leiserson, Rivest, and Stein (sect. 9.1, p. 214).

The book also states (in the form of an exercise) that the lower bound for any simultaneous min/max algorithm is $\lceil 3n/2 \rceil - 2$ comparisons in the worst case, so we actually can't do much better than we already do.

Answer 3

Just scan the array, starting with provisional maximum and minimum as the first element, from the second element onwards. If the element is larger than your current maximum, record that; if not, see if it is smaller than your current minimum, and update. You don't need the whole paraphernalia of splitting and recursion.

Can't have a simpler program. Can't do with less work, need to compare with at least $n - 1$ elements to confirm the maximum. For any order in which you check, by ordering the elements to be checked in decreasing order, you can force $2 (n - 1)$ comparisons.