Max and Min Finding

Here our problem is to find the minimum and maximum items in a set of n elements. We will see two methods here first one is iterative version and the next one uses divide and conquer strategy to solve the problem.

Iterative Algorithm:


MinMax(A,n)

{

max = min = A[0];

for(i = 1; i <n; i++}

{

if(A[i] > max)

max = A[i];

if(A[i] < min}

min = A[i];

}

}


The above algorithm requires 2(n-1) comparison in worst, best, and average cases. The comparison A[i] < min is needed only when A[i] > max is not true. If We replace the content inside the for loop by
if(A[i] >1nax)
max = A[i];
else if(A[i] < min)
m.i_n = A[i];
Then the best case occurs when the elements are in increasing order with (n-1) comparisons and worst case occurs when elements are in decreasing order with 2(n-1) comparisons. For the average case A[i] > max is about half of the time so number of comparisons is 3n/2 — 1.
We can clearly conclude that the time complexity is O[n].

 C Program For Mini Max Search


#include <stdio.h>


#include <stdlib.h>


#include <time.h>


#define SIZE 1000


void MinMax(int *arr, int l, int h, int *max, int *min)


{


    int max1, min1;


    if (l == h) { // case I - only one item


        *max = *min = arr[0];


    }


     else if (l == h - 1) { // case II - when there are two elements


        if (arr[l] > arr[h])


        {


            *max = arr[l];


            *min = arr[h];


        }


        else {


            *max = arr[h];


            *min = arr[l];


        }


    }


     else { // case - III


        int mid = (l + h) / 2; // Divide


        MinMax(arr, l, mid, max , min); // conquer


        MinMax(arr, mid+1, h, &max1 , &min1); //conquer


        if(*max < max1) *max = max1; //combine


        if(*min > min1) *min = min1;  //combine


    }


}


int main(int argc, char const *argv[])


{


    int arr[SIZE], n;


    clock_t start, end;


    double total_time = 0.00;


    int min, max;


    printf("Enter number of elements : ");


    scanf("%d", &n);


    for (int i = 0; i < n; i++)


    {


        arr[i] = rand() % 1000;


    }


    start = clock();


    MinMax(arr, 0, n-1, &max, &min);


    end = clock();


    printf("Min element :  %d\nMax element : %d\n", min, max);


    total_time += (double)(end - start) / CLOCKS_PER_SEC;


    printf("Execution time : %f seconds", total_time);


    return 0;


}

Output

Mini-Max Search


Share To:

Arogya Thapa Magar

Post A Comment:

0 comments so far,add yours