为什么binary search用beg+(end-beg)/2计算mid?

binary search中计算mid=(beg+end)/2与mid=beg+(end-beg)/2的区别?

这两种写法应该都见过,突然想起了这个问题,自己没想出来什么结果,感觉没有不同。后来再各种论坛问了问,结果都没能说出什么道理,还是stackoverflow比较牛,刚post上去没两分钟就给出来了答案。以后多逛逛stackoverflow吧。
http://stackoverflow.com/questions/20998982/whats-the-difference-between-mid-begend-2-and-mid-begend-beg-2-in-binary

  1. 对于0<=beg<=end,第一种写法与第二种数学上得到的结果是完全一样的,这个可以通过取整函数的方法证明。或者分为四种情况分别讨论。但是beg+end操作很可能会出现溢出的风险,但是后一种写法不会出现比end要大的中间数据,所以比较安全。(关于俩个结果相等也可以用足够大的数据写单元测试验证)
  2. c++stl源码的一些版本用的也是第二种,因为考虑了通用性,用第一种如果beg和end是指针或者迭代器的话是无法编译通过的,因为指针和迭代器运算不支持相加运算,却支持相减运算,所以第二种通用性强。(迭代器的话要求是随机访问迭代器random access iterator)。
    基本就是这两点原因了,这个问题也是c++primer fifth edition 3.26 上问到的。