Fastest way of finding the middle value of a triple?

Question

Given is an array of three numeric values and I'd like to know the middle value of the three.

The question is, what is the fastest way of finding the middle of the three?

My approach is this kind of pattern - as there are three numbers there are six permutations:

if (array[randomIndexA] >= array[randomIndexB] &&
    array[randomIndexB] >= array[randomIndexC])

It would be really nice, if someone could help me out finding a more elegant and faster way of doing this.

Solution 1

If you are looking for the most efficient solution, I would imagine that it is something like this:

if (array[randomIndexA] > array[randomIndexB]) {
  if (array[randomIndexB] > array[randomIndexC]) {
    return "b is the middle value";
  } else if (array[randomIndexA] > array[randomIndexC]) {
    return "c is the middle value";
  } else {
    return "a is the middle value";
  }
} else {
  if (array[randomIndexA] > array[randomIndexC]) {
    return "a is the middle value";
  } else if (array[randomIndexB] > array[randomIndexC]) {
    return "c is the middle value";
  } else {
    return "b is the middle value";
  }
}

This approach requires at least two and at most three comparisons. It deliberately ignores the possibility of two values being equal (as did your question): if this is important, the approach can be extended to check this also.

Solution 2

There's an answer here using min/max and no branches (https://stackoverflow.com/a/14676309/2233603). Actually 4 min/max operations are enough to find the median, there's no need for xor's:

median = max(min(a,b), min(max(a,b),c));

Though, it won't give you the median value's index...

Breakdown of all cases:

a b c
1 2 3   max(min(1,2), min(max(1,2),3)) = max(1, min(2,3)) = max(1, 2) = 2
1 3 2   max(min(1,3), min(max(1,3),2)) = max(1, min(3,2)) = max(1, 2) = 2
2 1 3   max(min(2,1), min(max(2,1),3)) = max(1, min(2,3)) = max(1, 2) = 2
2 3 1   max(min(2,3), min(max(2,3),1)) = max(2, min(3,1)) = max(2, 1) = 2
3 1 2   max(min(3,1), min(max(3,1),2)) = max(1, min(3,2)) = max(1, 2) = 2
3 2 1   max(min(3,2), min(max(3,2),1)) = max(2, min(3,1)) = max(2, 1) = 2

Solution 3

It's possible to answer the query without branches if the hardware can answer min and max queries without branches (most CPUs today can do this).

The operator ^ denotes bitwise xor.

Input: triple (a,b,c)
1. mx=max(max(a,b),c)
2. mn=min(min(a,b),c)
3. md=a^b^c^mx^mn
4. return md

This is correct because:

• xor is commutative and associative
• xor on equal bits produces zero
• xor with zero doesn't change the bit

The appropriate min/max functions should be chosen for int/float. If only positive floats are present then it's possible to use integer min/max directly on the floating point representation (this could be desirable, since integer operations are generally faster).

In the unlikely scenario that the hardware doesn't support min/max, it's possible to do something like this:

max(a,b)=(a+b+|a-b|)/2
min(a,b)=(a+b-|a-b|)/2

However, this isn't correct when using float operations since the exact min/max is required and not something that's close to it. Luckily, float min/max has been supported in hardware for ages (on x86, from Pentium III and onwards).

Solution 4

This can be done with two comparisons at most.

int median(int a, int b, int c) {
    if ( (a - b) * (c - a) >= 0 ) // a >= b and a <= c OR a <= b and a >= c
        return a;
    else if ( (b - a) * (c - b) >= 0 ) // b >= a and b <= c OR b <= a and b >= c
        return b;
    else
        return c;
}

Solution 5

And one more idea. There are three numbers {a,b,c}. Then:

middle = (a + b + c) - min(a,b,c) - max(a,b,c);

Of course, we have to remember about numeric limits...

View more solutions