How to find max. and min. in array using minimum comparisons?

algorithm, arrays, language-agnostic

Solution

1. Pick 2 elements(a, b), compare them. (say a > b)
2. Update min by comparing (min, b)
3. Update max by comparing (max, a)

This way you would do 3 comparisons for 2 elements, amounting to `3N/2` total comparisons for `N` elements.

Problem

This is a interview question: given an array of integers find the max. and min. using minimum comparisons. Obviously, I can loop over the array twice and use `~2n` comparisons in the worst case but I would like to do better.

Original source