= Simultaneous minimum and maximum
{title2=$\lceil3n/2\rceil-2$}
The minimum and maximum of a nonempty <array> can be found with at most $\lceil3n/2\rceil-2$ pairwise comparisons. Compare consecutive pairs once, retaining smaller entries as minimum candidates and larger entries as maximum candidates. If an entry is unpaired, put it into both candidate sets. Each candidate set has $\lceil n/2\rceil$ entries, and finding one extremum on $r$ entries uses $r-1$ comparisons. Thus the total is $\lfloor n/2\rfloor+2(\lceil n/2\rceil-1)$, equal to the stated bound; the singleton case uses zero. Balanced <divide-and-conquer algorithms> can perform both candidate reductions. Pairing is important: arbitrary equal splitting with only a two-element base case does not attain this comparison count at every size.
Back to article page
