Given a list of elements find max and min with no more than 3(n/2) comparisons, where n is the number of elements.

// Finding minimum and maximum simultaneously can be done in 3(n/2) comparisons
// by reading the input in pairs, comparing them with each other, then comparing 
// the smaller input with the current minimum and the larger input with the 
// current maximum. 
pair<int, int> MinMax(vector<int> &arr)
{
    if (0 == arr.size())
        throw "Bad Input!";
    if (1 == arr.size())
        return make_pair(arr[0], arr[0]);
 
    int min = INT_MAX;
    int max = INT_MIN;
    int start = 0;
    int end = arr.size() - 1;
    
    while (start < end)
    {
        if (arr[start] < arr[end])
        {
            if (arr[start] < min)
                min = arr[start];
            else if (arr[end] > max)
                max = arr[end];
        }
        else
        {
            if (arr[end] < min)
                min = arr[end];
            else if (arr[start] > max)
                max = arr[start];
        }
 
        start++;
        end--;
    }
 
    return make_pair(min, max);
}