CODEWITHSUNDEEP
c++algorithmc++11maxmin
Vincent
Vincent

Reputation: 60391

Get mid value in C++

Consider three values x, y, z.

What would be the formula to get the mid value (not the mean value but the value which is neither the min nor the max)?

const double min = std::min(x, std::min(y, z));
const double mid = /* what formula here ? */
const double max = std::max(x, std::max(y, z));

Upvotes: 13

Views: 4730

Answers (6)

digvijay91
digvijay91

Reputation: 697

The answer from this link shared in the comments:

const double mid = std::max(std::min(x,y),std::min(std::max(x,y),z));

Edit - As pointed out by Alan, I missed out on a case. I have given now a more intuitive proof.

Direct Proof: Without Loss of Generality with respect to x and y.
Starting with the innermost expression, min(max(x,y),z) ...

  1. If it returns z, we have found the relations: max(x,y) > z. Then the expression evaluates to max(min(x,y),z). Through this we are able to determine the relation between min(x,y) and z.
    If min(x,y) > z, then z is smaller than x and y both (as the relation becomes: max(x,y) > min(x,y) > z). Therefore the min(x,y) is indeed the median and max(min(x,y),z) returns that.
    If min(x,y) < z, then z is indeed the median (as min(x,y) < z < max(x,y)).

  2. If it returns x, then we have x < z and y < z. The expressions evaluates to: max(min(x,y),x). Since max(x,y) evaluated to x, min(x,y) evaluates to y. Getting the relation z > x > y. We return the max of x and y (as the expression becomes max(y,x)) which is x and also the median. (Note that the proof for y is symmetrical)

Proof Ends

Old Proof - Note it is NOT complete (Direct):

Without loss of generality: Assume x > y > z
Min of x and y is y. And min of (max of x and y) and z is z.
The max of y and z is y which is the median.

Assume x = y > z
Min of x and y say is x. And min of (max of x and y is x) and z is z.
Max of the above two is x, which is the median.

Assume x > y = z
Min of x and y is y. And min of (max of x and y is x) and z is z.
Max of the above two is y, which is the median.

Finally, assume x = y = z
Any of the three numbers will be the median., and the formula used will return some number.

Upvotes: 13

Ricky65
Ricky65

Reputation: 1687

The best way to do this is with a generic median function template. No copying, swapping or mathematical operations are required.

template <typename T>
const T& median(const T& a, const T& b, const T& c)
{
    if (a < b)
        if (b < c)
            return b;
        else if (a < c)
            return c;
        else
            return a;
    else if (a < c)
        return a;
    else if (b < c)
        return c;
    else
        return b;
}

Upvotes: 3

keyser
keyser

Reputation: 19189

A variant of Alan's "cheat" that (kind of and sometimes) prevents overflow:

#include <iostream>
#include <algorithm>

using namespace std;
int main(int argc, char *argv[]) {
    double a = 1e308;
    double b = 6e306;
    double c = 7.5e18;

    double mn = min(a,min(b,c));
    double mx = max(a,max(b,c));
    double avg = mn + (mx-mn)*0.5;
    double mid = a - avg + b - avg + c;

    cout << mid << endl;
}

Output:

6e+306

It makes use of the avg-formula often used in binary search to prevent overflow:

The average of two values can be calculated as low + (high-low)/2

However, it only works for positive values. Possible fallbacks include Alan's answer, or simply (x+y)/2 for the avg calculation.

Note that double precision comes into play here, and may cause issues in the mid-calculation. It works really well for positive integers though :)

Upvotes: 3

L&#225;szl&#243; Papp
L&#225;szl&#243; Papp

Reputation: 53165

It is a bit uglier than Alan's trick, but it cannot cause overflow, nor numerical errors, and so on:

int x, y, z, median;
...

if (x <= y && y <= z || y >= z && y <= x) median = y;
else if (y <= x && x <= z || x >= z && x <= y) median = x;
else median = z;

The algorithm is simply this:

  • check if x is between y and z, if yes, that is it.

  • check if y is between x and z, if yes, that is it.

  • It must be z since it was neither x, nor y.

=====================================================

You could also get this more flexibly if you have more than three elements, with sorting.

// or xor implementation, does not matter...

void myswap(int* a, int* b) { int temp = *b; *b = *a; *a = temp; }

int x, y, z;
// Initialize them
int min = x;
int med = y;
int max = z;

// you could also use std::swap here if it does not have to be C compatible
// In that case, you could just pass the variables without the address operator.
if (min > med) myswap(&min, &med);
if (med > max) myswap(&med, &max);
if (min > med) myswap(&min, &med);

Upvotes: 4

n. m. could be an AI
n. m. could be an AI

Reputation: 119877

To find all three at once in a symmetrical fashion:

min = x; med = y; max = z;

if (min > med) std::swap(min, med);
if (med > max) std::swap(med, max);
if (min > med) std::swap(min, med);

Upvotes: 13

Alan Stokes
Alan Stokes

Reputation: 18964

This seems like cheating, but: x + y + z - min - max

Upvotes: 12

Related Questions