快速排序中两种数组中间索引计算方式的差异

这是个非常好的问题——这种看似细微的差别，其实藏着很重要的整数溢出坑，很多开发者（哪怕有经验的）都会忽略这点！

核心差异：整数溢出风险 #

这两种写法在大多数场景下结果完全一致，但当lowerIndex和higherIndex都是非常大的整数时，会出现本质区别：

• 对于写法 array[(lowerIndex+higherIndex)/2]：
  当lowerIndex和higherIndex的和超过当前整数类型（比如int）的最大值时，会发生整数溢出，导致计算出的索引完全错误，甚至变成负数，直接引发数组越界访问的bug。
  举个实际例子：假设int的最大值是2147483647，如果lowerIndex = 2147483640，higherIndex = 2147483640，那么lowerIndex+higherIndex = 4294967280，远超int的上限，溢出后会变成负数，再除以2得到的索引自然也是无效的。
• 对于写法 array[lowerIndex+(higherIndex-lowerIndex)/2]：
  这个写法巧妙地避开了溢出问题。因为快速排序中higherIndex >= lowerIndex是必然成立的，所以higherIndex-lowerIndex的结果一定是非负的，而且不会超过int的最大值（两个数的差不可能比其中任何一个数更大）。之后加上lowerIndex，结果就是正确的中间索引，完全不会有溢出风险。

常规场景下的一致性 #

当lowerIndex和higherIndex的和没有超过整数类型的最大值时，两种写法的计算结果是完全相同的。我们可以用代数推导验证：

lowerIndex + (higherIndex - lowerIndex)/2 = (2*lowerIndex + higherIndex - lowerIndex)/2 = (lowerIndex + higherIndex)/2

因为整数除法会自动截断小数部分，所以两种写法在无溢出时等价。

为什么快速排序里更推荐前者？ #

在快速排序的场景中，我们无法保证lowerIndex和higherIndex不会取到接近整数上限的值（比如处理超大数组时），所以使用lowerIndex+(higherIndex-lowerIndex)/2是更健壮、更安全的写法，能避免潜在的溢出bug——这也是它在很多经典代码示例中出现的原因。

内容的提问来源于stack exchange，提问作者Nicky