# Min-max in array

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 `n` representing the length of `v`
• The second line consists of `n` numbers separated by space which represent the array `v`.

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;
if(r-l==1){ //if array has exactly 1 element -> min==max
min_max=min_max=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<min_max_r)
min_max=min_max_l;
else
min_max=min_max_r;
if(min_max_l>min_max_r)
min_max=min_max_l;
else
min_max=min_max_r;
//min_max==min(v[l,...,r-1]), min_max==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<<" "<<min_max<<endl;
}

```