计算中值时的安全性：mid = (left + right) / 2 与 mid = left + (right - left) / 2 的区别

导言

最近在使用二分算法的时候，发现取中间值有两种方案，并且两种方案带来的数据安全性是不同的，于是有了这篇博客。

在编程中，计算一个区间中间位置的常见方式是通过两个指针 left 和 right 来确定。通常，我们会使用如下公式来找到中点：

mid = (left + right) / 2

然而，这种常见的计算方式可能会导致问题，特别是在处理大数字时。为了解决这个问题，另一个常用的计算中点的公式是：

mid = left + (right - left) / 2

那么，为什么这两种写法会有所不同？它们有什么潜在的风险？让我们深入了解这两种计算方式的区别及其背后的原因。

mid = (left + right) / 2：潜在的溢出问题

首先，来看看经典的中点计算方式 mid = (left + right) / 2。它的工作原理非常简单，就是通过 left 和 right 两个变量相加，然后除以 2，得到它们的平均值，也就是中点。

但在一些编程语言中，尤其是 C、C++ 和 Java，Javascript等，当 left 和 right 是非常大的整数时，left + right 的结果可能会超出数据类型的范围，导致溢出。这意味着程序可能会计算出错误的中点值，从而影响后续的计算。

溢出的例子

考虑如下情况：

int left = 2147483647; // 32位整数的最大值

int right = 2147483647; // 32位整数的最大值

int mid = (left + right) / 2;

在上面的代码中，left + right 的结果是 4294967294，而 32 位整数的最大值是 2147483647。这显然超出了最大整数值，导致溢出，最终的结果是不准确的。

溢出带来的后果

错误的中点计算会影响很多算法的结果，尤其是涉及二分查找、合并排序等需要精确计算中间位置的算法。错误的中点可能导致程序进入无限循环或不必要的迭代，增加算法的时间复杂度。在某些情况下，溢出还可能导致程序崩溃。

mid = left + (right - left) / 2：避免溢出的方法

为了避免溢出问题，我们采用另一种更安全的计算中点的方式：

int mid = left + (right - left) / 2;

这种方法与前者的区别在于，它避免了直接将 left 和 right 相加，而是先计算 right - left 的差值，再将其除以 2，并加上 left。这样，即使 left 和 right 都是非常大的数，right - left 的差值通常不会超出整数的范围。

为什么这种方式更安全？

避免溢出：通过先计算差值，再加上 left，我们避免了 left 和 right 相加可能导致的溢出。保持精度：这种方式能够保证在最大值范围内计算出正确的中点，而不会受到数据类型限制。

举个例子

假设我们仍然使用 left = 2147483647 和 right = 2147483647 作为测试值，使用 mid = left + (right - left) / 2 就不会发生溢出，计算过程如下：

计算 right - left，得到 0。将 0 / 2 结果为 0，然后加上 left，得到 2147483647。

结果是正确的，而且没有溢出。

总结：为什么推荐使用 mid = left + (right - left) / 2

虽然 mid = (left + right) / 2 是最常见的写法，它在一些情况下可能会导致整数溢出。而 mid = left + (right - left) / 2 通过避免直接相加，确保了更高的安全性。对于处理大数或边界值时，这种写法更为推荐，尤其是在需要进行二分查找、归并排序等操作时。