为什么在计算数组的中间值时比较喜欢start +(end – start)/ 2 over(start + end)/ 2?

我见过程序员使用公式

mid = start + (end - start) / 2 

而不是使用更简单的公式

 mid = (start + end) / 2 

用于查找数组或列表中的中间元素。

为什么他们使用前者?

有三个原因。

首先,即使你使用的是指针, start + (end - start) / 2可以工作,只要end - start不会溢出1

 int *start = ..., *end = ...; int *mid = start + (end - start) / 2; // works as expected int *mid = (start + end) / 2; // type error, won't compile 

其次,如果startend都是大的正数, start + (end - start) / 2将不会溢出。 对于带符号的操作数,溢出未定义:

 int start = 0x7ffffffe, end = 0x7fffffff; int mid = start + (end - start) / 2; // works as expected int mid = (start + end) / 2; // overflow... undefined 

(请注意, end - start可能会溢出,但只有当start < 0end < 0

或者用无符号算术,溢出被定义,但给你错误的答案。 但是,对于无符号操作数,只要end >= startstart + (end - start) / 2将永远不会溢出。

 unsigned start = 0xfffffffeu, end = 0xffffffffu; unsigned mid = start + (end - start) / 2; // works as expected unsigned mid = (start + end) / 2; // mid = 0x7ffffffe 

最后,你经常想要start元素。

 int start = -3, end = 0; int mid = start + (end - start) / 2; // -2, closer to start int mid = (start + end) / 2; // -1, surprise! 

脚注

1根据C标准,如果指针减法的结果不能表示为ptrdiff_t ,那么行为是不确定的。 但是,实际上,这需要使用至less一半的整个地址空间来分配char数组。

我们可以举一个简单的例子来certificate这个事实。 假设在一个特定的数组中,我们试图find范围[1000, INT_MAX]的中点。 现在, INT_MAXint数据types可以存储的最大值。 即使加1 ,最终的值也会变成负数。

此外, start = 1000end = INT_MAX

使用公式: (start + end)/2

中点将是

(1000 + INT_MAX)/2 = -(INT_MAX+999)/2 ,如果我们尝试使用这个值进行索引,

但是,使用公式(start + (end-start)/2) ,我们得到:

(1000 + (INT_MAX-1000)/2) = (1000 + INT_MAX/2 - 500) = (INT_MAX/2 + 500)

要增加别人已经说过的话,第一个解释清楚那些不那么具有math意义的人:

 mid = start + (end - start) / 2 

读作:

中间等于开始加上长度的一半。

然而:

 mid = (start + end) / 2 

读作:

中间等于开始加上结束的一半

这似乎不像第一个那么清楚,至less当这样expression时。

正如科斯指出的那样,它也可以这样写:

中等等于开始和结束的平均值

哪一个更清楚,但至less在我看来,还是不如第一个清楚。