Yes it can:
min-max(a[], n)
if a[1] < a[2]
min = a[1]
max = a[2]
else
min = a[2]
max = a[1]
for i = 3 to n
if min > a[i]
min = a[i]
else if max < a[i]
max = a[i]
return min, max
This version requires 2*(n - 2) + 1 = 2n - 3 comparisions. To make the question more precise: can the reduction in comparisons be made a factor of the size of the input array?
This page last modified on 24 January 2006.