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[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;
}

References


Related posts

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s