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.

Corinnecorinth

luckily the answer stays the same whether you compare ints or floats :-) – Pock

Median-of-three pivot selection for QuickSort? – Osana

could also be QuickSelect – Taxi

Answer 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.

Hierophant

It's kind of ugly, and I think the OP was looking for an elegant solution. The trick is lots of people mistake fewer characters for more elegant, when in reality, more straightforward (this answer) is more readily optimizable by the compiler/virtual machine. – Sharpset

Even if this code is 18 lines; it's effective. Put it in a function and simply call it when needed. – Fregoso

Answer 2

There's an answer here using min/max and no branches (https://mcmap.net/q/341942/-fastest-way-of-finding-the-middle-value-of-a-triple). 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

Vano

This code is pretty impressive, only 4 min/max used to achieve it. – Fregoso

it works even if some of the values are equal – Brachiopod

Thanks for the code! Finally found one elegant code for median of three! – Wizardry

Insight into this answer: when you have a function clamp(x,L,H) = max(L,min(H,x)), the median of 3 is clamp(c, min(a,b), max(a,b)). – Beehive

that's an awesome implementation, thanks! useful for vectors – Loriloria

@Řrřola Cool! It seems to be fastest and shortest way in C++. Not sure Java has clamp function... – Cotidal

Answer 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).

Cypsela

What does b+|a mean? Both + and | are binary operators. – Precedential

It's just an expansion of min and max functions by using absolute value. |a-b| means absolute value of a-b. Either way, I'd recommend the answer given below by Gyorgy (https://mcmap.net/q/341942/-fastest-way-of-finding-the-middle-value-of-a-triple) which is more neat than mine. – Cypsela

min = (a < b) ? (a < c) ? a : c : (b < c) ? b : c; and max = (a > b) ? (a > c) ? a : c : (b > c) ? b : c; – Sacrarium

@Cypsela I find your solution much more easier to understand than solution by Gyorgy. But the most surprising is that if I compile these solutions with gcc 7.2 -O3 your solution is twice faster. With clang 4.0 Gyorgy's solution is marginally faster than yours and both of them are 15% faster than best of gcc. – Bleachers

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

Sumption

Did you try median(INT_MIN,INT_MAX,0) ? I get INT_MAX on a two-complement machine... – Foltz

Yes, this is susceptible to integer overflow. I wouldn't recommend this in production as it's written because of that. – Sumption

Using ((long)b - c) in the second condition allows reuse of ((long)a - b). – Philhellene

Answer 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...

Bulley

Don't get it. Java doesn't have a min() or max() that takes 3 arguments. – Ultramicroscopic

It's rather an idea how to solve the problem, not the exact solution – Bulley

@Ultramicroscopic min(a,b,c) = min(a,min(b,c)) – Melodimelodia

for min/max with 3 arguments you'll need to make again 2 or 3 comparisons, so no reall performance in such a solution – Marathi

Answer 6

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.

Tranquillity

hey... your first answer was completely different using min and max. Why change it? I thought it was a good approach – Bret

@reinier ... it wasn't my answer. – Tranquillity

stephen: euh? was it a removed answer from someone else? ah oh well... maybe it didn't work and they removed it or something – Bret

You do not need to do so many comparison - expand this to if-else statemetns and you can see you have a layer too much of "?"'s. – Autotomize

@reinier: it was 'Stephan202' who deleted his answer. – Osana

Should be: (a <= b) ? ((b <= c) ? b : ((a < c) ? c : a)) : ((a <= c) ? a : ((b < c) ? c : b)) – Mosby

You cannot avoid having at least 5 conditionals, unless you do things like value swapping or recursion. This is because the corresponding decision tree has 6 leaves, which means 5 internal nodes, thus 5 decision points in the whole code, though only two or three of them will be active at a time, those in the path to the answer leaf. But maybe the size of the code, or at least the number of conditionals, can be reduced by using swapping or other techniques! – Mosby

@StephenC that comment was a left-over dating from before the update, I removed it. – Pock

Answer 7

I didn't see a solution which implements swaps:

int middle(int a, int b, int c) {
    // effectively sort the values a, b & c
    // putting smallest in a, median in b, largest in c

    int t;

    if (a > b) {
        // swap a & b
        t = a;
        a = b;
        b = t;
    }

    if (b > c) {
        // swap b & c
        t = b;
        b = c;
        c = t;

        if (a > b) {
            // swap a & b
            t = a;
            a = b;
            b = t;
        }
    }

    // b always contains the median value
    return b;
}

Sacrarium

Do not understand why this solution not on top, because it has only 2 or 3 compares and easy to understand. – Lorant

Answer 8

Bumping up an old thread, but still it's the shortest solution, and nobody mentioned it.

Solution:

int median2(int a, int b, int c) {
    return (a > b) ^ (a > c) ? a : (a > b) ^ (b > c) ? c : b;
}

Tests:

(tests cover all the possible combinations, all of them print 6)

public static void main(String[] args) {

    System.out.println(median(3, 6, 9));
    System.out.println(median(3, 9, 6));
    System.out.println(median(6, 3, 9));
    System.out.println(median(6, 9, 3));
    System.out.println(median(9, 3, 6));
    System.out.println(median(9, 6, 3));
    System.out.println(median(6, 6, 3));
    System.out.println(median(6, 6, 9));
    System.out.println(median(6, 3, 6));
    System.out.println(median(6, 9, 6));
    System.out.println(median(3, 6, 6));
    System.out.println(median(9, 6, 6));
    System.out.println(median(6, 6, 6));

}

Explanation 1

(a > b) ^ (a > c) false if either c > a > b or c < a < b - return a;

otherwise (a > b) ^ (b > c) false if either a > b > c or a < b < c - return b;

otherwise return c;

Explanation 2

Let's assume p = a > b; q = b > c; s = a > c;

Let's build a Karnaugh map.

   | 00  01  11  10 (p, q)
---+----------------------
 0 |  b   c   *   a
 1 |  *   a   b   c
(s)|

* means that the combination is impossible (like a > b; b > c; a < c)

Notice that the right part is a mirrored left part, and the map can be simplified by introducing t = p ^ q; u = s ^ p

   |  0   1 (t)
---+---------
 0 |  b   c  
 1 |  *   a  
(u)|

So the function may be written as

private static int median(int a, int b, int c) {
    boolean t = (a > b) ^ (b > c);
    boolean u = (a > b) ^ (a > c);
    if (u)
        return a;
    else if (t)
        return c;
    else
        return b;
}

Inlining variables and replacing ifs with ?: gives the answer

int median2(int a, int b, int c) {
    return (a > b) ^ (a > c) ? a : (a > b) ^ (b > c) ? c : b;
}

The solution works fine even if some on the inputs are equal, which may be not evident, but quite logical.

Zaragoza

Answer 9

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 (Fastest way of finding the middle value of a triple?) to see an example of this. The many code line does not necessarily turn out to be larger code than nested questionmark-colon's.

Galactic

Answer 10

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.

Granville

Answer 11

median = (a+b+c) - Math.min(Math.min(a,b),c) - Math.max(Math.max(a,b),c)

This is the basic one, i don't know how efficient this would work but these functions use if conditions after all. If you would like you can turn this statement into if-else statements, yet it will take time. Why so lazy?

Perilune

Answer 12

Based on the excellent answer from Gyorgy, you can get the median's index without branches by replacing min/max with conditional moves:

int i = (array[A] >= array[B]) ? A : B;
int j = (array[A] <= array[B]) ? A : B;
int k = (array[i] <= array[C]) ? i : C;
int median_idx = (array[j] >= array[k]) ? j : k;

javac should generate a ConditionalNode for each of these ternary assignments, which translate to cmp/cmov pairs in assembly. Also note the comparisons were chosen such that in case of equality, the first index in alphabetical order is returned.

Saddlebow

This is some seriously screwed up code and certainly is not valid Java. What is (array[A] < array[B]) * 4? The first part returns a boolean value because of > but 4 is an integer and the operator * doesn't work on a boolean and an integer. It seems like you have an interesting idea and I'd like to hear you explain it, but with nothing further this answer is so low quality I will be flagging it if no edits are made. – Ultramicroscopic

My bad, this was a clumsy C habit. My previous solution involved computing the boolean expression (a<b) to integer using ((a-b) >>> 31) (graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign), then creating a three-bits number from the three comparisons (a<b), (a<c) and (b<c), and using that number to index a String[8] array. But that was before thinking about conditional moves! – Saddlebow

Answer 13

Method 1

int a,b,c,result;
printf("enter three number");
scanf("%d%d%d",&a,&b,&c);
result=a>b?(c>a?a:(b>c?b:c)):(c>b?b:(a>c?a:c));
printf("middle %d",result);

Method 2

int a=10,b=11,c=12;
//Checking for a is middle number or not
if( b>a && a>c || c>a && a>b )
{
    printf("a is middle number");
}

//Checking for b is middle number or not
if( a>b && b>c || c>b && b>a )
{
    printf("b is middle number");
}

//Checking for c is middle number or not
if( a>c && c>b || b>c && c>a )
{
    printf("c is middle number");
}

Method 3

if(a>b)
{
    if(b>c)
    {
        printf("b is middle one");
    }
    else if(c>a)
    {
        printf("a is middle one");
    }
    else
    {
        printf("c is middle one");
    }
}
else
{
    if(b<c)
    {
        printf("b is middle one");
    }
    else if(c<a)
    {
        printf("a is middle one");
    }
    else
    {
        printf("c is middle one");
    }
}

I got appropriate ans of finding the middle value of a triple

Viable

Answer 14

The easiest way is through sorting. For example consider this code :

import java.util.Arrays;


int[] x = {3,9,2};
Arrays.sort(x); //this will sort the array in ascending order 

//so now array x will be x = {2,3,9};
//now our middle value is in the middle of the array.just get the value of index 1
//Which is the middle index of the array.

int middleValue = x[x.length/2]; // 3/2 = will be 1

That's it.It's that much simple.

In this way you don't need to consider the size of the array.So if you have like 47 different values then you can also use this code to find the middle value.

Rinarinaldi

Answer 15

This one will work:

template<typename T> T median3_1_gt_2(const T& t1, const T& t2, const T& t3) {
    if (t3>t1) {
        return t1;
    } else {
        return std::max(t2, t3);
    }
}
template<typename T> T median3(const T& t1, const T& t2, const T& t3) {
    if (t1>t2) {
        return median3_1_gt_2(t1, t2, t3);
    } else {
        return median3_1_gt_2(t2, t1, t3);
    }
}

https://github.com/itroot/firing-ground/blob/864e26cdfced8394f8941c8c9d97043da8f998b4/source/median3/main.cpp

Hasidism

Answer 16

    if(array[aIndex] > array[bIndex]) {
        if(array[bIndex] > array[cIndex]) return bIndex;
        if(array[aIndex] > array[cIndex]) return cIndex;
        return aIndex;
    } else {
        if(array[bIndex] < array[cIndex]) return bIndex;
        if(array[aIndex] < array[cIndex]) return cIndex;
        return aIndex;
    }

Dinnie

Answer 17

largest=(a>b)&&(a>c)?a:(b>c?b:c);
smallest=(a<b)&&(a<c)?a:(b<c?b:c);
median=a+b+c-largest-smallest;

Romanticize

Can you please explain your answer ? – Tattle

I don't know why,but I thought that the largest,median and the smallest of 3 numbers should be found.But it can be the answer(maybe not the best).But only with one variable(better for memory) median=a+b+c-(a>b)&&(a>c)?a:(b>c?b:c)-(a<b)&&(a<c)?a:(b<c?b:c); I think next variant is better, but harder for reading(even using more brackets) median= (a>=b)&&(a>=c)?(b>c?b:c):(((a/b)*b+(a/c)*c)>a?((a/b)*b+(a/c)*c):a); This variant only for integers(if a<b => a/b==0) – Romanticize

Answer 18

// Compute median of three values, no branches

int median3(int V[3])
{
  unsigned int A,B,C;
  
  A=(V[0] < V[1]);
  B=(V[1] < V[2]);
  C=(V[0] < V[2]);

  return V[(B^C)<<1 | (A^B^1)];
  
}

Rubberneck

While this code may resolve the OP's issue, it is best to include an explanation as to how your code addresses the OP's issue. In this way, future visitors can learn from your post, and apply it to their own code. SO is not a coding service, but a resource for knowledge. Also, high quality, complete answers are more likely to be upvoted. These features, along with the requirement that all posts are self-contained, are some of the strengths of SO as a platform, that differentiates it from forums. You can edit to add additional info &/or to supplement your explanations with source documentation. – Tanager

Answer 19

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.

Pock

This gives the minimum value, rather than the middle one. – Hierophant

Lol, did you try it? first line sets indexAB to the maximum of A and B, second line sets indexMiddle to the minimum of that maximum and C, giving you the middle value. I guess you missed the "index_B_ : index_A_" part of the first line? – Pock

Except that if C is the smallest value, this will produce C rather than the middle value. – Forename

Sorry, no, I didn't try it, and you're right, I misread it. My apologies. However, the point is that you can't do it in just two comparisons, as illustrated by jk above. – Hierophant

Oops, you are correct. I replaced it with a solution I beleive is correct now :-) – Pock

Answer 20

You can use array, like this:

private static long median(Integer i1, Integer i2, Integer i3) {

    List<Integer> list = Arrays.asList(
            i1 == null ? 0 : i1,
            i2 == null ? 0 : i2,
            i3 == null ? 0 : i3);

    Collections.sort(list);
    return list.get(1);
}

Baileybailie

Answer 21

Here is the answer in Python, but same logic applies to the Java program.

def middleOfThree(a,b,c):
    middle = a
    if (a < b and b < c) or (c < b and b < a):
        middle = b 
    elif (a < c and c < b) or (b < c and c < a):
        middle = c    
    print 'Middle of a=%d, b=%d, c=%d is %d' % (a,b,c,middle)

middleOfThree(1,2,3)
middleOfThree(1,3,2)
middleOfThree(2,1,3)
middleOfThree(2,3,1)
middleOfThree(3,2,1)
middleOfThree(3,1,2)

Secundines

Answer 22

100% branch-free version for integers:

int mid(const int a, const int b, const int c) {
    const int d0 = b - a;
    const int m = (d0 >> 31);
    const int min_ab = a + (d0 & m);
    const int max_ab = a + (d0 & ~m);
    const int d1 = c - max_ab;
    const int min_max_ab_c = max_ab + (d1 & (d1 >> 31));
    const int d2 = min_ab - min_max_ab_c;
    return min_ab - (d2 & (d2 >> 31));
}

Constructed using the branch-free min / max functions:

int min(const int a, const int b) { const int d = b - a; return a + (d & (d >> 31)); }
int max(const int a, const int b) { const int d = a - b; return a - (d & (d >> 31)); }

It may not look pretty but the machine code might prove more efficient on some architectures. Especially those without min / max instructions. But I have not made any benchmarks to confirm it.

Tirzah

Answer 23

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

Bret

Firstly, this gives a value, rather than an index. Secondly, for a[0] < a[1] < a[2] it gives a[2] as the answer, which is incorrect. – Hierophant

Answer 24

A lot of these seem to be using pretty complex if statements. I've found a really simple workaround using the Math library.

Math.max(Math.min(array[start], array[mid]), Math.min(array[start], array[mid], array[end]))

Works out quite nicely.

Alecto

Consider the array (1, 2, 3). This would produce the output 1. Which is not the middle value. – Groningen

Answer 25

It can be solved in one line by the ternary operator

int middle(int A, int B, int C) {
      return (A>B&&A>C)?B>C?B:C:(B>C&&B>A)?A>C?A:C:B;
}

Malena

Hello and welcome to StackOverflow. Please, when posting an answer to a question check proper code formatting and next time don't post your answer all in caps. Thanks. – Scoter

In execution, this is may take five sequential comparisons: how is this the Fastest way of finding the middle value of a triple? – Philhellene