| Max-Min Search |
Max-Min search problem aims at finding the smallest as well as the biggest element in a vector A of n elements.
Following the steps of Divide and Conquer the vector can be divided into sub-problem as shown below.
The search has now reduced to comparison of 2 numbers. The time is spent in conquering and comparing which is the major step in the algorithm.
Algorithm: Max-Min (p, q, max, min)
{
If (p = q) Then
max = a(p)
min = a(q)
Else
If ( p � q-1) Then
If a(p) > a(q) Then
max = a(p)
min = a(q)
Else
max = a(q)
min = a(p)
If End
Else
m ¬
(p+q)/2
max-min(p,m,max1,min1)
max-min(m+1,q,max2,min2)
max ¬
large(max1,max2)
min ¬
small(min1,min2)
If End
If End
Algorithm End.
Illustration
Consider a data set with elements {82,36,49,91,12,14,06,76,92}. Initially the max and min variables have null values. In the first call, the list is broken into two equal halves.. The list is again broken down into two. This process is continued till the length of the list is either two or one. Then the maximum and minimum values are chosen from the smallest list and these values are returned to the preceding step where the length of the list is slightly big. This process is continued till the entire list is searched. The detail description is shown in fig 4.1
|
