Question 32

Let the list contain $n$ distinct elements. We need to find an element $x$ that is neither the maximum nor the minimum of the list.

Pick any 3 distinct elements from the list, say $a, b, c$:

1. Compare $a$ and $b$ (1 comparison).
2. Compare the winner and loser with $c$ (at most 2 additional comparisons).

The median of $\{a, b, c\}$ is strictly greater than $\min(a, b, c)$ and strictly less than $\max(a, b, c)$:

• Because it is strictly greater than at least one element in the list, it cannot be the global minimum.
• Because it is strictly less than at least one element in the list, it cannot be the global maximum.

Hence, the median of the 3 chosen elements is guaranteed to be neither the global minimum nor the global maximum. The number of comparisons required is at most 3, which is independent of $n$: