find三重中间值的最快方法是？

给定是三个数值的数组，我想知道这三个数的中间值。

问题是， find三者中 最快的方法是什么？

我的方法是这种模式 – 有三个数字，有六个排列：

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

如果有人能帮我find一个更优雅 ， 更快捷的方法，这将是非常好的。

Answer 1

如果你正在寻找最有效的解决scheme，我会想象它是这样的：

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

这种方法至less需要两次，最多三次比较。 它刻意忽略了两个值是平等的可能性（如同你的问题一样）：如果这个问题很重要的话，这个方法也可以扩展到检查这个问题。

Answer 2

有一个答案在这里使用最小/最大和没有分支（ https://stackoverflow.com/a/14676309/2233603 ）。 实际上4分钟/最大操作就足以find中位数，不需要异或：

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

虽然，它不会给你中位数的指数…

所有情况的细分：

 abc 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 

Answer 3

如果硬件可以在没有分支的情况下回答最小和最大查询（现在大多数CPU可以做到这一点），那么可以在没有分支的情况下回答查询。

运算符^表示按位异或。

 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 

这是正确的，因为：

• xor是交换和关联的
• 异或位上的xor产生零
• xor与零不改变位

应该为int / floatselect适当的最小/最大函数。 如果只有正浮点数，则可以直接在浮点表示上使用整数最小/最大值（这可能是可取的，因为整数运算通常更快）。

在不太可能的情况下，硬件不支持最小/最大，可以做这样的事情：

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

但是，在使用浮动操作时这是不正确的，因为需要确切的最小/最大值，而不是靠近它。 幸运的是，浮点最小值/最大值在硬件上已经被支持了很多年（在Pentium III以上的x86上）。

Answer 4

这最多可以用两个比较来完成。

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

Answer 5

还有一个想法。 有三个数字{a,b,c} 。 然后：

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

当然，我们必须记住数字限制…

Answer 6

以下是如何使用唯一条件来表示这个问题：

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

EDITS：

1. 以上错误发现@Pagas已被修复。
2. @Pagas也指出，如果你只使用条件，你不能用less于5的条件来做到这一点，但你可以使用临时variables或值交换来减less它。
3. 我想补充一点，很难预测纯粹的条件解决scheme还是分配解决scheme会更快。 这可能取决于JIT有多好，但是我认为条件版本对于优化器来说更容易分析。

Answer 7

我没有看到实现交换的解决scheme：

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

Answer 8

你最好直接写下来。 如你所说，只有六种可能性。 没有合理的方法会变得更快或更慢，所以只要去看一些容易阅读的东西。

我想用min（）和max（）来简洁，但是我认为三个嵌套if / thens是一样的好。

Answer 9

如果您必须从符合某些标准的X值中找出一个，则您必须至less将该值与每个X-1其他值进行比较。 对于三个值，这意味着至less两个比较。 既然这是“find不是最小的而不是最大的价值”，那么只有两个比较就可以逃脱。

然后，您应该专注于编写代码，以便您可以清楚地了解所发生的事情并保持简单。 这里这意味着嵌套if。 这将允许JVM在运行时尽可能地优化这个比较。

查看Tim提供的解决scheme（ find三重中间值的最快方法 ）来查看这个例子。 许多代码行不一定是比嵌套的questionmark-colon更大的代码。

Answer 10

这一个将工作：

 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

Answer 11

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

Answer 12

 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; 

Answer 13

方法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); 

方法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"); } 

方法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"); } } 

我得到适当的答案find一个三重的中间值

Answer 14

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

这是最基本的一个，我不知道这个工作效率如何，但是如果条件毕竟的话，这些函数会使用。 如果你愿意，你可以把这个语句变成if-else语句，但这需要时间。 为什么这么懒惰？

Answer 15

最简单的方法是通过sorting。 例如考虑这个代码：

 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 

就是这样，这很简单。

这样你就不需要考虑数组的大小。所以如果你有47个不同的值，那么你也可以使用这个代码来find中间值。

Answer 16

这里是Python的答案，但同样的逻辑适用于Java程序。

 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) 

Answer 17

基于Gyorgy的出色答案，通过用条件移动replacemin / max，可以得到没有分支的中位数索引：

 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应该为这些三元赋值中的每一个生成ConditionalNode，这些赋值在汇编中转换为cmp/cmov对。 还要注意，select比较是为了在平等的情况下，按字母顺序返回第一个索引。

Answer 18

在idry中使用idxA，

 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指向中间值。

说明：从3最小值2开始是整体最小值，其他值必须是中间值。 因为我们检查相等性，所以我们可以比较最后一行的索引，而不必比较数组的值。

Answer 19

你可以像这样使用数组：

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

Answer 20

很多这些似乎使用相当复杂的if语句。 我发现一个非常简单的解决方法，使用math库。

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

工作很好。

Answer 21

整数的100％分支版本：

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

使用无分支min / max函数构造：

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

它看起来可能不太好，但机器代码在某些架构上可能会更有效率。 特别是那些没有最小/最大指示。 但是我还没有做出任何基准来证实这一点。

Answer 22

或者用于查找包含中间值的数组中的索引：

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