C Program For Mini-Max Search | C Programming

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


Post a Comment

0 Comments