二分查找的问题,对于 mid=beg+(end-beg)/2 与 mid=(beg+end)/2 区别?

一直觉得二分查找虽然实现简单,但是很多坑,最近看到这两种不同的写法,好像除了说第一种写法可以避免溢出之外,这两种写法还有什么不同吗?问题见中文版c++ primer 第五版101页习题3.26,为什么不用第二种写法?

阅读 5.5k
1 个回答

很简单。这个如果是数组下标还行的通,但如果是指针,那beg+end这个操作本身就有炸范围的风险。

另外从概念上,end-beg这个操作,得到的是有序序列中两个元素的距离增量。所以最后的逻辑能够分解为:求距离增量,然后折半,最后加回基址上边去。

beg+end这个操作本身得到的值,并没有明确的意义。所以虽然在数学上两个式子并没有区别,但如果追究求表达式的分步运算,则后一个式子存在意义不明确的运算操作,可读性和概念性上都差一点。

至于避免溢出的问题,原谅偷懒,根据你的要求,在此回答中就完全不做考虑了。:D

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题