MinMax

Find a min and a max from an array of n integers.

Solution:

Use 1 temp place holders for min and max each. Compare each element of array with this number.

This would require (n-1) * 2 = 2n-2 comparisons.

Better Solution:

Recursive. Divide and Conquer. Divide array into two, further into two. At end, compare two elements. One of them is min and other is max (from these two). Hint: This is the reason of saving the comparisons as you got min and max in single comparison.

It would require 3n/2 -2 comparisons.

Reference:

1. Lec 05 - Design and Analysis of Algorithms - NPTEL