Java Reference
In-Depth Information
/
**
@returnTheminimumandmaximumvaluesinA
betweenpositionslandr
*
/
staticvoidMinMax(intA[],intl,intr,intOut[]){
if(l==r){ //n=1
Out[0]=A[r];
Out[1]=A[r];
}
elseif(l+1==r){//n=2
Out[0]=Math.min(A[l],A[r]);
Out[1]=Math.max(A[l],A[r]);
}
else{ //n>2
int[]Out1=newint[2];
int[]Out2=newint[2];
intmid=(l+r)/2;
MinMax(A,l,mid,Out1);
MinMax(A,mid+1,r,Out2);
Out[0]=Math.min(Out1[0],Out2[0]);
Out[1]=Math.max(Out1[1],Out2[1]);
}
}
Figure15.3
Recursive algorithm for finding the minimum and maximum values
in an array.
For example, what if we have six items in the list? If we break the list into two
sublists of three elements, the cost would be 8. If we break the list into a sublist of
size two and another of size four, then the cost would only be 7.
With divide and conquer, the best algorithm is the one that minimizes the work,
not necessarily the one that balances the input sizes. One lesson to learn from this
example is that it can be important to pay attention to what happens for small sizes
of n, because any division of the list will eventually produce many small lists.
We can model all possible divide-and-conquer strategies for this problem with
the following recurrence.
8
<
0 n = 1
1 n = 2
min
1kn1
fT(k) + T(nk)g + 2 n > 2
T(n) =
:
That is, we want to find a way to break up the list that will minimize the total
work. If we examine various ways of breaking up small lists, we will eventually
recognize that breaking the list into a sublist of size 2 and a sublist of size n 2
will always produce results as good as any other division. This strategy yields the
following recurrence.
8
<
0 n = 1
1 n = 2
T(n 2) + 3 n > 2
T(n) =
:
