在二分搜索中计算中点索引

Question

因此,mid在二进制搜索中计算的正确方法是mid = low + ((high - low) / 2)为了处理溢出错误.

我的实现使用无符号的64位变量,我从来没有看到我的数组变得如此之大以至于导致溢出的情况.我是否仍然需要使用上述实现或我可以使用mid = (low + high) / 2

这里最好的做法是什么？

Answer 1

如果没有溢出的可能性,计算中点的溢出安全方法在技术上是不必要的:如果您愿意,可以使用不安全的公式.但是,无论如何,将它保留在那里可能是一个好主意,以防你的程序有一天被修改以打破你的假设.我认为添加单个CPU指令以使您的代码面向未来是对代码可维护性的巨大投资.

Answer 2

查看本文几乎所有二进制搜索和合并都是破碎的

更好的实践(今天)

可能更快,可以说明确的是:6:int mid =(low + high)>>> 1;

在那之后 :

在C和C++中(你没有>>>运算符),你可以这样做:6:mid =((unsigned int)low +(unsigned int)high))>> 1;

最后:

2008年2月17日更新:感谢芬兰诺基亚研究中心工程人员Antoine Trux指出最初提出的C和C++修正案(第6行)不能保证符合相关C99标准(国际标准) - ISO/IEC - 9899 - 第二版 - 1999-12-01,3.4.3.3),其中说如果添加两个有符号的数量并获得溢出,则结果是未定义的.在这方面,较旧的C标准,C89/90和C++标准都与C99相同.现在我们已经做了这个改变,我们知道程序是正确的;)

最重要的是,总会有一个不起作用的情况

Answer 3

Don Knuth 的方法通过位掩码完美地工作，不可能发生溢出：

return (low & high) + ((low ^ high) >> 1)

编辑：low + high = (low ^ high) + (low & high) << 1

第 19 页，计算机编程艺术，卷。4、唐纳德·E·高德纳