找到中间点的最佳方法

Question

在许多算法中，我看到人们使用两种不同的方式来获得中间点。

1. （低+高）/2
2. 低+（高-低）/2

大多数情况下，我在 QuickSort 中看到过第二种方法。找到两个数字之间的中间值的最佳方法是什么？为什么？

Answer 1

这完全取决于上下文，但我将针对第 2 种情况提出一个案例并解释原因。

我们首先假设您选择第 1 种情况，即：

(LOW + HIGH) / 2

这看起来完全合理，而且从数学上来说，确实如此。让我们代入两个数字并查看结果：

(12345 + 56789) / 2

结果是 34567。看起来不错不是吗？

现在的问题是，在计算机中，事情并不那么简单。你还有一些需要data types应对的事情。通常这用位数之类的东西来表示。换句话说，您可能有一个 32 位数字，或一个 16 位数字，或一个 64 位数字，等等。

所有这些都具有所谓的合法值范围，即。“这些类型将持有什么样的价值观”。一个 8 位无符号数（这意味着它不能为负数）可以保存 2 的 8 个不同值的幂，即 256。一个 16 位无符号值可以保存 65536 个值，或者范围从 0 到 65535。值有符号，它们从 -half 到 +half-1，这意味着对于 8 位有符号值，它将从 -128 到 +127；对于有符号 16 位值，它将从 -32768 到 +32767。

那么现在我们回到原来的公式。如果我们用于计算的数据类型不足以容纳怎么办LOW + HIGH？

例如，假设我们为此使用 16 位有符号值，并且我们仍然得到这个表达式：

(12345 + 56789) / 2

12345可以保存为16位值（小于65536），与56789相同，但结果如何呢？12345 和 56789 相加的结果是 69134，比 65535（最高无符号 16 位值）大。

那么它会发生什么呢？有两个结果：

1. 它会溢出，这意味着它将从 0 开始向上计数，这意味着它实际上最终会得到 3598 的结果(123456 + 56789) - 65536
2. 它会抛出异常或类似的异常，从而导致程序因溢出问题而崩溃。

如果我们得到第一个结果，则(12345 + 56789)/2变为3598/2or 1799。显然不正确。

那么，如果我们使用另一种方法呢：

12345 + (56789-12345)/2

首先，让我们添加括号：56789-12345等于44444，一个可以以 16 位数据类型保存的数字。

添加后12345 + 44444得到56789，一个也可以以 16 位数据类型保存的数字。

除以567892 得到28934.5. 由于我们可能在这里处理“整数” 28934（通常，除非您的特定世界四舍五入）。

因此，选择第二个表达式高于第一个表达式的原因是，它不必以相同的方式处理溢出，并且对此类问题更具弹性。

事实上，如果你想一想，你可以拥有的最大第二个值就是你的数据类型可以拥有的最大合法值，所以这种表达式：

X + (Y-X)

...假设 X 和 Y 都是相同的数据类型，最多可以是该数据类型的最大值。基本上，它根本不必应对溢出。