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