Fastest way of finding the middle value of a triple?

Question

I've got the following scenario:

There are three ("pseudo" randomly chosen) int or float values which represent indices of an array. Now I'd like to compare the appropriate values from that array. After having compared them I'd like to know the middle value of the three and use this specific element for some further array operations.

The question is, what is the fastest way of finding the middle of the three within Java? My idea was this kind of pattern - as there are three numbers there are 6 possible permutations. Obviously, there is some ugly overhead and the flow of control isn't really that clearly laid out...

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

It would be really nice, if someone could help me out with a better and faster way of doing this. Even a plain logical form with clauses would be a nice thing...
Have a nice weekend anyway :D

Answer 1

Here's how you can express this using only conditionals:

int a, b, c = ...
int middle = (a <= b) 
    ? ((b <= c) ? b : ((a < c) ? c : a)) 
    : ((a <= c) ? a : ((b < c) ? c : b));

EDITS:

1. Errors in above found by @Pagas have been fixed.
2. @Pagas also pointed out that you cannot do this with fewer than 5 conditionals if you only use conditional, but you can reduce this using temporary variables or value swapping.
3. I would add that it is hard to predict whether a pure conditional or assignment solution would be faster. It is likely to depend on how good the JIT is, but I think the conditional version would be easier for the optimizer to analyse.

Answer 2

Using idxA to idxC in ary,

int ab = ary[idxA] < ary[idxB] ? idxA : idxB;
int bc = ary[idxB] < ary[idxC] ? idxB : idxC;
int ac = ary[idxA] < ary[idxC] ? idxA : idxC;

int idxMid = ab == bc ? ac : ab == ac ? bc : ab;

indexMiddle points to the middle value.

Explanation: from the 3 minima 2 are the overall minimum and the other value must be the middle. Because we check equality we can compare the indices in the last line instead of having to compare the array values.

Answer 3

or a one liner for finding the index in the array containing the middle value:

 int middleIndex = (a[0]<a[1]) ? ((a[0]<a[2) ? a[2] : a[0]) : ((a[1]<a[2) ? a[2] : a[1]);

Answer 4

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.

Answer 5

If you must find one out of X values satisfying some criteria you have to at least compare that value to each of the X-1 others. For three values this means at least two comparisons. Since this is "find the value that is not the smallest and not the largest" you can get away with only two comparisons.

You should then concentrate on writing the code so you can very clearly see what goes on and keep it simple. Here this means nested if's. This will allow the JVM to optimize this comparison as much as possible at runtime.

See the solution provided by Tim (http://stackoverflow.com/questions/1582356/fastest-way-of-finding-the-middle-value-of-a-tripel/1582524#1582524) to see an example of this. The many code line does not necessarily turn out to be larger code than nested questionmark-colon's.

Answer 6

You might as well write this in the most straightforward, way. As you said, there are only six possibilities. No reasonable approach is going to be any faster or slower, so just go for something easy to read.

I'd use min() and max() for conciseness, but three nested if/thens would be just as good, I think.