Finding the Maximum and Minimum

Let us consider another simple problem that can be solved by the divide and conquer technique. The problem is to find the maximum and minimum items in a set of n elements.Algorithm 4 is a straight forward algorithm to accomplish this.

Straight Max Min requires 2(n = 1) element comparisons in the best, average, and worst cases. An immediate improvement is possible by realizing that the comparison a[i] < min is necessary only when a[i] > max is false. Hence we can replace the contents of the for loop by

Now the best case occurs when the elements are in increasing order. The number of element comparisons is n – 1. The worst case occurs when the elements are in decreasing order. In this case the number of element comparisons is 2(n-1). The average number of element comparisons is less than 2(n – 1).On the average,a[i]is greater than max half the time,and so the average number of comparisons is 3n/2- 1.

A divide-and-conquer algorithm for this problem would proceed as follows: Let P = (n,a[i],…, a[j]) denote an arbitrary instance of the problem. Here n is the number of elements in the list a[i],…, a[j]and we are interested in finding the maximum and minimum of this list.Let Small(P)/be true when n <2.In this case,the maximum and minimum area[i] if n = 1. If n = 2, the problem can be solved by making one comparison.

If the list has more than two elements,P has to be divided into smaller instances.For example,we might divide P into the two instances P1 = ([n/2],a[1],…,a[[n/2]]) and P2 = (n -[n/2],a[[n/2\]+1],… ,a[n]). After having divided P into two smaller sub problems, we can solve them by recursively invoking the same divide-and-conquer algorithm.How can we combine the solutions for P1 and P2 to obtain a solution for P? If MAX(P) and MIN(P) are the maximum and minimum of the elements in P, then MAX(P) is the larger of MAX(P1) and MAX(P2). Also, MIN(P) is the smaller of MIN(P1)and MIN(P2)

Algorithm 5 results from applying the strategy just described. Max Min is a recursive algorithm that finds the maximum and minimum of the set of elements{a(i),a(i + 1),…, a(j)}.The situation of set sizes one (i = j) and two (i = j-1) are handled separately. For sets containing more than two elements,the mid point is determined(just as in binary search)and two new sub problems are generated.When the maxima and minima of these sub problems are determined,the two maxima are compared and the two minima are compared to achieve the solution for the entire set.

The procedure is initially invoked by the statement MaxMin(l,n,x,y) Suppose we simulate MaxMin on the following nine element.

A good way of keeping track of recursive calls is to build a tree by adding a node each time a new call is made. For this algorithm each node has four items of information:i,j, max,and rain. On the array a[] above,the tree of Figure 1 is produce.