Question

USING C++. The following divide-and-conquer algorithm is proposed for finding the simultaneous maximum and minimum:

If there is one item, it is the maximum and minimum, and if there are two items, then compare them, and in one comparison
you can find the maximum and minimum.

Otherwise, split the input into two halves, divided as evenly as possibly (if N is odd, one of the two halves will have
one more element than the other). Recursively find the maximum and minimum of each half, and then in two additional comparisons produce the maximum and minimum for the entire problem.

Write the above function which will take in a vector and solve the problem, returning a vector of two elements, the min and max.

Write a main method for testing your program.

Answer 1

The program for finding maximum and minimum using divide and conquer is as follows:

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

// Divide & Conquer solution to find minimum and maximum number in a vector
void findMinAndMax( vector<int> a, int low, int high, int& min, int& max)
{
        // if vector contains only one element

        if (low == high)                        // common comparison
        {
                if (max < a[low])     // comparison 1
                        max = a[low];

                if (min > a[high])   // comparison 2
                        min = a[high];

                return;
        }

        // if vector contains only two elements

        if (high - low == 1)                    // common comparison
        {
                if (a[low] < a[high])        // comparison 1
                {
                        if (min > a[low])     // comparison 2
                                min = a[low];

                        if (max < a[high])   // comparison 3
                                max = a[high];
                }
                else
                {
                        if (min > a[high])   // comparison 2
                                min = a[high];

                        if (max < a[low])     // comparison 3
                                max = a[low];
                }
                return;
        }

        // find mid element
        int mid = (low + high) / 2;

        // recur for left sub-vector
        findMinAndMax(a, low, mid, min, max);

        // recur for right sub-vector
        findMinAndMax(a, mid + 1, high, min, max);
}

int main()
{
        vector<int> a = { 7, 2, 9, 3, 1, 6, 7, 8, 4 };
        int n = sizeof(a) / sizeof(a[0]);
        int max,min;

        findMinAndMax(a, 0, n - 1, min, max);

        cout << "The minimum element in the array is " << min << '\n';
        cout << "The maximum element in the array is " << max;

        return 0;
}