Given an array v of n numbers, where n=2k, k>0 be a natural number, find the minimum and maximum element in v. There are no assumptions regarding the orders of the elements of v. A basic iterative approach would require 2(n-1) comparisons (n-1 comparisons to find the minimum and n-1 comparisons to find the maximum). However, your program MUST perform at most 3/2n-1 comparisons.
Difficulty: Easy.
Input
There are two lines.
- The first line contains an integer
nrepresenting the length ofv - The second line consists of
nnumbers separated by space which represent the arrayv.
At the end of each line, there are no extra spaces, and there is a \n.
Output
One line containing 2 numbers separated by space, which are the smallest and biggest elements in v respectively.
Example
Input:
8
3 1 6 8 5 9 -2 7
Output:
-2 9
Hint
You can use a divide-and-conquer paradigm.
Solution: C++
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
using namespace std;
int* find_min_max(int v[], int l, int r){
//find min and max in v[l,..,r-1]
int* min_max = new int[2];
if(r-l==1){ //if array has exactly 1 element -> min==max
min_max[0]=min_max[1]=v[l];
return min_max;
}
int s=(r-l)/2+l;
int* min_max_l=find_min_max(v, l, s); //find min_max in v[l,...,s-1]
int* min_max_r=find_min_max(v, s, r); //find min_max in v[s,...,r-1]
if(min_max_l[0]<min_max_r[0])
min_max[0]=min_max_l[0];
else
min_max[0]=min_max_r[0];
if(min_max_l[1]>min_max_r[1])
min_max[1]=min_max_l[1];
else
min_max[1]=min_max_r[1];
//min_max[0]==min(v[l,...,r-1]), min_max[1]==max(v[l,..,r-1])
return min_max;
}
int main(){
int n;
cin>>n; //length of the array
int v[n];
for(int i=0; i<n; i++)
cin>>v[i];
int *min_max = find_min_max(v, 0, n);
cout<<min_max[0]<<" "<<min_max[1]<<endl;
}
KejiTech 