= Solution
For one element, return it as both extrema without a comparison. Otherwise compare consecutive pairs once, put each smaller element in a candidate <array> $L$ and each larger element in a candidate <array> $H$. If one element is unpaired, put it in both candidate arrays. This <simultaneous minimum and maximum> construction computes the minimum of $L$ and maximum of $H$ by balanced <divide-and-conquer algorithms>: split the candidate array, recursively find the desired extremum in each half, and compare the two returned values. These extremum routines use one comparison per merge and therefore $r-1$ comparisons on $r$ candidates.
Every element excluded from $L$ is at least its paired element, so a global minimum remains in $L$; likewise a global maximum remains in $H$. The recursive extremum routines are correct by <structural induction>. For even $n=2m$, there are $m$ pair comparisons and two searches on $m$ candidates, giving
$$
C(2m)=m+2(m-1)=3m-2.
$$
For odd $n=2m+1\geq3$, there are $m$ pair comparisons and two searches on $m+1$ candidates, giving
$$
C(2m+1)=m+2m=3m.
$$
Together with $C(1)=0$, both cases give
$$
\boxed{C(n)\leq\left\lceil\frac{3n}{2}\right\rceil-2}.
$$
For powers of two, the equivalent direct <divide-and-conquer algorithm> returns the ordered pair of extrema for each half, then combines the two minima with one comparison and the two maxima with one comparison. Its base cases must include $C(2)=1$, rather than performing two unnecessary comparisons on a pair. The <recurrence relation> is $C(n)=2C(n/2)+2$ for $n\geq4$, whence $C(n)=3n/2-2$. Arbitrary near-equal splitting without the initial pairing can exceed the desired comparison bound for other values of $n$; the pairing construction above handles every positive size.
Back to article page
