Introduction

Finding the minimum and maximum values within an array is a fundamental task that arises in various applications. Whether you are dealing with data analysis, sorting algorithms and much more. In this chapter we will delve into different algorithms for finding the min-max values in an array.

Problem Understanding

The problem at hand is straightforward: given an array of elements, we need to identify both the minimum and maximum values within the array. The challenge lies in devising algorithms that can accomplish this task optimally considering factors such as time and space complexity.

Algorithms

Brute Force Method | Naive Approach:

The simplest approach involves iterating through the entire array and keeping track of the minimum and maximum values. This method has a time complexity of O(n), where n is the size of the array.

Divide and Conquer:

A more efficient approach involves using a divide-and-conquer strategy. The array is divided into two halves, and the minimum and maximum of each half are computed recursively. The final min and max are then obtained by comparing the results from the two halves.

Tournament Method:

The tournament method involves pairing elements in the array and finding the minimum and maximum within each pair. These min and max values are then compared to determine the overall minimum and maximum.

Code Implementation

Naive Approach

#include <iostream>
using namespace std;

void findMinMaxNaive(int arr[], int size, int& min, int& max) {
    min = INT_MAX;
    max = INT_MIN;

    for (int i = 0; i < size; ++i) {
        if (arr[i] < min) min = arr[i];
        if (arr[i] > max) max = arr[i];
    }
}

int main() {
    int arr[] = {3, 1, 8, 5, 9, 2};
    int size = sizeof(arr) / sizeof(arr[0]);

    int min, max;
    findMinMaxNaive(arr, size, min, max);

    cout << "Minimum: " << min << endl;
    cout << "Maximum: " << max << endl;

    return 0;
}

Divide and Conquer

#include <iostream>
using namespace std;

struct MinMax {
    int min;
    int max;
};

MinMax findMinMaxDivideConquer(int arr[], int low, int high) {
    MinMax result, left, right;
    int mid;

    // Base case: one element
    if (low == high) {
        result.min = arr[low];
        result.max = arr[low];
        return result;
    }

    // Base case: two elements
    if (high == low + 1) {
        result.min = min(arr[low], arr[high]);
        result.max = max(arr[low], arr[high]);
        return result;
    }

    // Divide the array into two halves
    mid = (low + high) / 2;
    left = findMinMaxDivideConquer(arr, low, mid);
    right = findMinMaxDivideConquer(arr, mid + 1, high);

    // Combine the results
    result.min = min(left.min, right.min);
    result.max = max(left.max, right.max);

    return result;
}

int main() {
    int arr[] = {3, 1, 8, 5, 9, 2};
    int size = sizeof(arr) / sizeof(arr[0]);

    MinMax result = findMinMaxDivideConquer(arr, 0, size - 1);

    cout << "Minimum: " << result.min << endl;
    cout << "Maximum: " << result.max << endl;

    return 0;
}

Tournament Method

#include <iostream>
using namespace std;

struct MinMax {
    int min;
    int max;
};

MinMax findMinMaxTournament(int arr[], int low, int high) {
    MinMax result, left, right;
    int mid;

    // Base case: one element
    if (low == high) {
        result.min = arr[low];
        result.max = arr[low];
        return result;
    }

    // Base case: two elements
    if (high == low + 1) {
        result.min = min(arr[low], arr[high]);
        result.max = max(arr[low], arr[high]);
        return result;
    }

    // Divide the array into two halves
    mid = (low + high) / 2;

    // Recursively find the min and max in each half
    left = findMinMaxTournament(arr, low, mid);
    right = findMinMaxTournament(arr, mid + 1, high);

    // Combine the results
    result.min = min(left.min, right.min);
    result.max = max(left.max, right.max);

    return result;
}

int main() {
    int arr[] = {3, 1, 8, 5, 9, 2};
    int size = sizeof(arr) / sizeof(arr[0]);

    MinMax result = findMinMaxTournament(arr, 0, size - 1);

    cout << "Minimum: " << result.min << endl;
    cout << "Maximum: " << result.max << endl;

    return 0;
}

Complexity Analysis

Naive Approach

• Time Complexity: O(n)
• Space Complexity: O(1)

Divide and Conquer

• Time Complexity: O(n)
• Space Complexity: O(log n)

Tournament Method

• Time Complexity: O(n)
• Space Complexity: O(log n)