为什么在计算数组的中间时更喜欢start +(end-start)/ 2 over(start + end)/ 2？

Question

我见过程序员使用这个公式

mid = start + (end - start) / 2

而不是使用更简单的公式

mid = (start + end) / 2

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

他们为什么使用前者呢？

Answer 1

有三个原因.

首先,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

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

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

(注意end - start可能会溢出,但仅限于start < 0或end < 0.)

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

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!

脚注

¹根据C标准,如果指针减法的结果不能表示为a ptrdiff_t,则行为未定义.但是,实际上,这需要char使用至少一半的整个地址空间来分配数组.

Answer 2

我们可以用一个简单的例子来证明这一事实.假设在某个大型数组中,我们试图找到该范围的中点[1000, INT_MAX].现在,INT_MAX是int数据类型可以存储的最大值.即使1添加到此,最终值也将变为负值.

还有,start = 1000和end = 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) 哪个不会溢出.

Answer 3

为了增加其他人已经说过的内容,第一个解释了那些数学意义较小的人的意义:

mid = start + (end - start) / 2

读作:

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

然而:

mid = (start + end) / 2

读作:

中等于开始加结束的一半

这似乎并不像第一个那样清晰,至少在表达时如此.

科斯指出它也可以读作:

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

哪个更清楚,但至少在我看来,仍然没有,与第一个一样清楚.