Joint min and max with about 3n/2 comparisons

Question

Given $n$ numbers, describe how to find both the smallest and the largest using no more than about $3n/2$ comparisons.

Short answer

Process the numbers in pairs. Compare the two members of each pair first ( $1$ comparison), then compare only the larger with the running maximum and the smaller with the running minimum ( $2$ more). That is $3$ comparisons per $2$ elements, about $3n/2-2$ in total, versus roughly $2n$ when each element is checked against both extremes separately.

Adapted from Zhou, A Practical Guide to Quantitative Finance Interviews, sec. 7.1 Algorithms, 'Search algorithm A', p.176; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Normal Distribution is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free