Optimal array max and min

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.

def getMinMax(r):
  mini = r[0]
  maxi = r[0]

  start = 0
  if len(r) % 2 != 0:
    start = 1

  for i in range(start,len(r)-1,2):
    n1 = r[i]
    n2 = r[i+1]

    # Exactly 3 comparisons each time
    if(n1 < n2):
      mini = min(n1,mini)
      maxi = max(n2,maxi)
    else:
      mini = min(n2,mini)
      maxi = max(n1,maxi)

  return [mini,maxi]