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