Find the Min and Max Simultaneously

Description:

Given an array, find the min and max of its elements.

Example:

Note

Idea:

如果直接扫，需要两遍，比较2n次。

分成小块，只要比较3n/2次。

Code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

pair<int, int> minMaxFind(vector<int> arr){
    int numMin=INT_MAX;
    int numMax=INT_MIN;

    for(int i=0; i<arr.size()/2; i++){
        int localMin=min(arr[2*i], arr[2*i+1]);
        int localMax=max(arr[2*i], arr[2*i+1]);
        numMin=min(localMin, numMin);
        numMax=max(localMax, numMax);
    }
    if(arr.size()%2 == 1){
        numMin=min(arr.back(), numMin);
        numMax=max(arr.back(), numMax);        
    }

    return pair<int,int>(numMin, numMax);
}

int main(){
    vector<int> arr={1,2,1,2,3,3,2,5,6};
    auto result = minMaxFind(arr);
    cout<<result.first<<' '<<result.second<<endl;
}