Minimum And Maximum Element - C++ Solution

1. Introduction

In this blog post, we address a common task in array processing: finding the minimum and maximum elements with the least number of comparisons. This problem is an excellent example of optimization in algorithm design.

Problem

Given a non-empty integer array, the objective is to identify the minimum and maximum elements by making the fewest possible comparisons and return them as a pair.

Example:

Input: [5, 7, 2, 4, 9, 6]

Output: (2, 9)

2. Solution Steps

1. Initialize variables to store the minimum and maximum values.

2. If the array has an odd number of elements, initialize min and max with the first element. If it has an even number of elements, initialize them with the smaller and larger of the first two elements, respectively.

3. Iterate over the array in pairs, comparing each pair among themselves and then with the current min and max.

4. Update the min and max values as needed.

5. Return the pair (min, max) after traversing the entire array.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to find the minimum and maximum elements in an array
pair<int, int> findMinAndMax(vector<int>& nums) {
    int n = nums.size();
    int minNum, maxNum, i;

    // Initialize min and max
    if (n % 2 == 0) {
        minNum = min(nums[0], nums[1]);
        maxNum = max(nums[0], nums[1]);
        i = 2; // Set starting index for loop
    } else {
        minNum = maxNum = nums[0];
        i = 1; // Set starting index for loop
    }

    // Iterate over the array in pairs
    while (i < n - 1) {
        if (nums[i] < nums[i + 1]) {
            minNum = min(minNum, nums[i]);
            maxNum = max(maxNum, nums[i + 1]);
        } else {
            minNum = min(minNum, nums[i + 1]);
            maxNum = max(maxNum, nums[i]);
        }
        i += 2; // Increment index by 2
    }

    return {minNum, maxNum};
}

int main() {
    vector<int> nums = {5, 7, 2, 4, 9, 6};
    auto [minNum, maxNum] = findMinAndMax(nums);
    cout << "Min: " << minNum << ", Max: " << maxNum << endl;
    return 0;
}

Output:

Min: 2, Max: 9

Explanation:

The findMinAndMax function efficiently finds the minimum and maximum elements in the array. It handles arrays with both odd and even lengths, initializing the min and max variables accordingly. The function then iterates through the array in pairs, making comparisons to update the min and max values. This approach reduces the number of comparisons needed, especially for large arrays, as seen in the output for the given example.