Write a program to find the maximum and minimum number using divide and conquer methods.

Name of the experiment:  Write a program to find the maximum and minimum number using divide and conquer methods.

Algorithm:

   1       Algorithm MaxMin(I,j,max,min)

   2       {

   3       if( i=j) then max:= min:=a[i];

   4       else if (i= j-1) then

   5                 {

   6                           if ( a[i] < a[j] then

   7                           {

   8                                    max:=a[j]; min:= a[i];

   9                           }

  10                        else

  11                        {

  12                                  max:= a[i]; min:= a[j];

  13                        }

  14               }

  15               else

  16               {

  18                        MaxMin(I, mid, max, min);

  19                        MaxMin(mid+1, j, max1, min1);

  20                        if (max<max1) then max:= ma1;

  21                        if (min> min1) then min:= min1;

  22               }

  23     }

Source  Code:

#include<stdio.h>

#include<stdio.h>

int max, min;

int a[100];

void maxmin(int i, int j)

{

 int max1, min1, mid;

 if(i==j)

 {

  max = min = a[i];

 }

 else

 {

  if(i == j-1)

  {

   if(a[i] <a[j])

   {

    max = a[j];

    min = a[i];

   }

   else

   {

    max = a[i];

    min = a[j];

   }

  }

  else

  {

   mid = (i+j)/2;

   maxmin(i, mid);

   max1 = max; min1 = min;

   maxmin(mid+1, j);

   if(max <max1)

    max = max1;

   if(min > min1)

    min = min1;

  }

 }

}

int main ()

{

 int i, num;

 printf ("\nEnter the total number of numbers : ");

 scanf ("%d",&num);

 printf ("Enter the numbers : \n");

 for (i=1;i<=num;i++)

  scanf ("%d",&a[i]);

 max = a[0];

 min = a[0];

 maxmin(1, num);

 printf ("Minimum element in an array : %d\n", min);

 printf ("Maximum element in an array : %d\n", max);

 return 0;

}

Sample Input and Output:

Enter the total number of numbers : 5

Enter the numbers :

29

21

64

27

20

Minimum element in an array : 20

Maximum element in an array : 64