The following divide-and-conquer algorithm is proposed for finding the simultane

Question

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, producing a vector of two elements, the min and max.kk

Explanation / Answer

The required divide and conquer technique can be implemented using recursive calls to a function which will be successively finding min and max values for the given section of vector.

Also we cannot return more than one value from a function so we will use a structure which will be storing two int's for min and max values respectively.

The working example can with results is available at https://ideone.com/DRS4Ia

#include <iostream>

#include <vector>

using namespace std;

//if one element its max and min

//divide an dconquer

struct values {

int max, min;

};

struct values findMinMax(vector<int> &a, int start, int end) {

if(start < end) {

int mid = (start + end) / 2;

//recursive calls on both halfs to get min, max values

struct values left_res = findMinMax(a, start, mid);

struct values right_res = findMinMax(a, mid+1, end);

//compare left and right values and set for min, max for entire length

struct values final_res;

final_res.min = min(left_res.min, right_res.min);

final_res.max = max(left_res.max, right_res.max);

return final_res;

} else {

//if only one value is there, then it is the both min, and max;

struct values final_res;

final_res.min = final_res.max = a[start];

return final_res;

}

}

int main() {

// your code goes here

static const int arr[] = {16,2,77,29};

int size = sizeof(arr) / sizeof(arr[0]);

vector<int> vec (arr, arr + size);

struct values res = findMinMax(vec, 0, size-1);

cout<<"min : " << res.min<<", "<<"max : "<<res.max<<endl;

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.