# Optimal array max and min

#### Posted on February 26, 2013

##### Last updated on February 28, 2013

Problem Statement:

Given an array of unsorted integers, find the maximum and minimum with the smallest number of comparisons.

The naive solution requires $$2n$$ comparisons, one pass for the maximum, and one pass for the minimum. We optimize the solution to $$3n/2$$ as follows. We process the array of elements in pairs $$(a,b)$$. If $$a$$ is smaller than $$b$$, update the minimum $$mini$$ to $$min(a,mini)$$, and maximum $$maxi$$ to $$max(b,maxi)$$. The other case is symmetrical. Since each time we do $$3$$ comparisons, and process $$n/2$$ elements, the total number of comparisons is $$\frac{3n}{2}$$.

Code in python follows. Also available as a gist. Notice that we need to handle the case when the number of elements is odd, to ensure that we can process the elements in pairs.

Markdown SHA1: 3d605d9853293aeae12e89f9d08b20156c1ef186