寻找三个值中间值的最快方法是什么？

Question

给定一个由三个数字组成的数组，我想知道其中间的值。

问题是，找出这三个数字中的中间数的最快方法是什么？

我的方法是这样的模式-因为有三个数字，所以有六种排列方式：

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

如果有人能帮我找到一种更优雅且更快速的方法，那真是太好了。

- Gnark

---

幸运的是，无论比较整数还是浮点数，答案都保持不变 :-) - rsp

快速排序的三数取中枢点选择？ - Jonathan Leffler

也可以是QuickSelect。 - talloaktrees

Answer 1

在这里有一个使用min/max而没有分支的答案(https://dev59.com/wXI-5IYBdhLWcg3w-9wK#14676309)。实际上，只需要4个min/max操作即可找到中位数，无需使用异或：

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

虽然它无法给出中位数的索引...

所有情况的详细说明:

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

- Gyorgy Szekely

---

这段代码相当不错，只使用了4个min/max就实现了它。 - Liggliluff

即使一些值相等，它可以正常工作。 - jfs

谢谢你的代码！终于找到了一个优雅的三数中位数代码！ - Nicholas Humphrey

当你有一个函数clamp(x, L, H) = max(L, min(H, x))时，求三个数的中位数可表示为clamp(c, min(a,b), max(a,b))。 - Řrřola

这是一个很棒的实现，谢谢！对于向量非常有用。 - DataGreed

@Řrřola 很酷！这似乎是 C++ 中最快最短的方式。不确定 Java 是否有夹紧函数... - 4LegsDrivenCat

Answer 2

如果硬件可以在没有分支的情况下回答min和max查询（大多数现代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与零不会改变比特位

应选择适当的min/max函数用于int/float类型。如果只有正的浮点数存在，则可以直接在浮点表示上使用整数min/max（这可能是有利的，因为整数操作通常更快）。

在硬件不支持min/max的不太可能的情况下，可以执行类似以下操作：

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

然而，在使用浮点数操作时，这不是正确的，因为需要精确的最小值/最大值，而不是接近它的值。幸运的是，浮点数的最小值/最大值在硬件上已经得到了支持很久了（在x86平台，从Pentium III及以后版本的处理器都支持）。

- Max

---

b+|a 的意思是什么？+ 和 | 都是二进制运算符。 - Ajay

这只是通过使用绝对值来扩展min和max函数。|a-b|表示a-b的绝对值。 无论如何，我建议使用Gyorgy（https://dev59.com/wXI-5IYBdhLWcg3w-9wK#19045659）下面给出的答案，比我的更整洁。 - Max

min = (a < b) ? (a < c) ? a : c : (b < c) ? b : c; and max = (a > b) ? (a > c) ? a : c : (b > c) ? b : c; - mckamey

@Max，我发现你的解决方案比Gyorgy的解决方案更容易理解。但最令人惊讶的是，如果我使用gcc 7.2 -O3编译这些解决方案，你的解决方案会快两倍。对于clang 4.0，Gyorgy的解决方案略微快于你的解决方案，它们都比最好的gcc快15%。 - Alexey Guseynov

Answer 3

如果你正在寻找最高效的解决方案，我认为它应该类似于这样：

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

这种方法至少需要两次比较，最多需要三次比较。它故意忽略了两个值相等的可能性（就像你的问题一样）：如果这很重要，该方法也可以扩展以检查这一点。

- Tim

---

这句话的意思是，“这样做有点丑陋，我认为原发帖人正在寻找更优雅的解决方案。关键在于，很多人错误地认为字符越少越优雅，但实际上，更简单（指这个答案）更容易被编译器/虚拟机进行优化。” - Karl

即使这段代码有18行，它也很有效。将其放入一个函数中，在需要时简单地调用它。 - Liggliluff

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

- Zach Conn

---

你尝试过 median(INT_MIN,INT_MAX,0) 吗？在补码机器上我得到了 INT_MAX... - aka.nice

是的，这个容易受到整数溢出的影响。因为这个原因，我不建议在生产环境中使用它。 - Zach Conn

在第二个条件中使用((long)b - c)可以重复使用((long)a - b)。 - greybeard

Answer 5

还有一个想法。有三个数字{a，b，c}。那么：

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

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

- jacek.ciach

---

不太理解。Java 没有接受 3 个参数的 min() 或 max() 函数。 - Celeritas

这更像是解决问题的_想法_，而不是确切的解决方案。 - jacek.ciach

@Celeritas min(a,b,c) = min(a,min(b,c)) - sim642

对于带有3个参数的min/max函数，您需要再进行2或3次比较，因此这种解决方案在性能上并没有真正的优势。 - radistao

Answer 6

这里是只使用条件语句表达这个内容的方法：

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

编辑：

1. 由@Pagas发现的上述错误已经被修正。
2. @Pagas还指出，如果仅使用条件语句，则无法少于5个条件语句来完成此操作，但可以使用临时变量或值交换来减少条件语句。
3. 我想补充一点，很难预测纯条件语句或赋值语句哪种解决方案更快。这可能取决于JIT的好坏，但我认为条件版本更容易让优化器进行分析。

- Stephen C

---

嘿，你的第一个回答完全不同，使用了最小值和最大值。为什么要改变它？我认为这是一个好的方法。 - Toad

@reinier...那不是我的答案。 - Stephen C

@reinier：删除回答的是“Stephan202”。 - Jonathan Leffler

除非您执行值交换或递归等操作，否则无法避免至少有5个条件语句。这是因为相应的决策树有6个叶子节点，意味着整个代码中有5个内部节点，因此有5个决策点，尽管其中只有两个或三个会同时激活，即通向答案叶子节点的路径上的那些决策点。但也许通过使用交换或其他技术可以减少代码的大小，或者至少减少条件语句的数量！ - Paggas

@StephenC 那个评论是更新之前的遗留物，我已经将其删除。 - rsp

Answer 7

我没有看到一个实现交换的解决方案：

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

- mckamey

---

不明白为什么这个解决方案没有排名靠前，因为它只有2或3个比较，并且易于理解。 - l0ki

Answer 8

顶一下旧帖，但它仍然是最简单的解决方案，并没有人提到过。

解决方案：

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

测试：

（测试覆盖所有可能的组合，所有测试都打印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));

}

解释 1

(a > b) ^ (a > c) 如果 c > a > b 或者 c < a < b 则为假 - 返回 a；

否则，(a > b) ^ (b > c) 如果 a > b > c 或者 a < b < c 则为假 - 返回 b；

否则返回 c；

解释 2

假设 p = a > b； q = b > c； s = a > c;

让我们构建一个卡诺图。

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

* 表示组合不可能（比如 a > b; b > c; a < c）。

请注意，右侧部分是左侧部分的镜像，并且可以通过引入 t = p ^ q; u = s ^ p 来简化映射。

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

因此，该函数可以写成：

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

内联变量和用?:替换if语句可以得到答案

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

该解决方案即使某些输入相等也能正常工作，这可能不太明显，但相当合理。

- ekaerovets

Answer 9

中位数 = (a+b+c) - Math.min(Math.min(a,b),c) - Math.max(Math.max(a,b),c)

这是基本的方法，我不知道它的效率如何，但这些函数毕竟使用了if条件语句。如果您愿意，可以将此语句转换为if-else语句，但这需要时间。为什么这么懒呢？

- Melih Yıldız'

Answer 10

如果您必须找到一个满足某些条件的X个值中的一个，那么您至少必须将该值与其他X-1个值进行比较。对于三个值，这意味着至少要进行两次比较。由于这是“找到不是最小值也不是最大值的值”，因此您只需要进行两次比较即可。

然后，您应该专注于编写代码，以便您可以非常清楚地看到发生了什么，并保持简单。在这里，这意味着嵌套的if语句。这将允许JVM在运行时尽可能优化此比较。

请参阅Tim提供的解决方案（查找三个数字中间值的最快方法？）以查看示例。许多代码行不一定比嵌套的问号-冒号更大。

- Thorbjørn Ravn Andersen