A friend of mine recently gave me the following problem:
Given an unsorted set of numbers find the minimum and maximum of set in a maximum of $1.5n$ comparisons.
My answer involves splitting the list up pairwise and finding the result on the only half of the set.
- Go through list and compare every even index to its immediate right (odd) index. Sort each pair numerically within itself. This step takes $\dfrac{1}{2}n$ comparisons.
- Find the minimum of every odd index and find the maximum of every even element using the typical algorithm. This step takes $n$ comparisons.
Note that this could be done in one pass by doing the pair comparison and the min/max comparison in one pass.
Is there a better way?
