java - 计算数组中间索引的差异？

Question

我一直在尝试解决 QuickSort 问题，并且遇到了一个我们选择主元元素作为中间元素的场景。

http://www.java2novice.com/java-sorting-algorithms/quick-sort/

 // calculate pivot number, I am taking pivot as middle index number
        int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];

这与下面获取中间索引的方法有何不同？

        int pivot = array[(lowerIndex+higherIndex)/2];

我记得我以前也看过很多次。而且我确信我错过了一个场景，当我们得到一个奇数或其他东西时，这很有用。

我尝试了几个示例值，但两种方式都得到了相同的响应。我错过了什么？

感谢您的回复。

Answer 1

更有可能是

(lowerIndex+higherIndex)/2

溢出而不是

lowerIndex+(higherIndex-lowerIndex)/2.

例如 lowerIndex == higherIndex == Integer.MAX_VALUE/2 + 1。

编辑:

表达式等价性的数学证明

l + (r - l)/2                            (in java notation)
  = l + round_towards_zero((r - l) / 2)  (in math notation)
  = round_towards_zero(l + (r - l) / 2)  (since l is an integer)
  = round_towards_zero((2 * l + r - l) / 2)
  = round_towards_zero(r + l) / 2)
  = (l + r) / 2                          (in java notation)