解释这些中点算法之间的区别

Question

为什么二进制搜索的中点算法使用

low + (high-low)/2

而不是

(low + high)/2

Answer 1

你的问题被标记为Python，所以我会回答Python。简而言之，它没有：

上面在文档中找到的pythonic 实现使用后一种结构。正如评论中的人们所指出的，某些语言需要尊重溢出。Python 不是其中之一，并且具有任意精度的整数。

在评论中，有人推测从类 C 语言移植的人可能会复制该语言更可接受的结构。这个有可能。还有人评论说，一个可能比另一个快；这种微观优化似乎很难总体上进行评论。

但是……如果他们不是整数怎么办！

我假设这些是整数，因为对于二分搜索，索引是整数。如果它们确实不是整数，那么使用它们访问数组时将会遇到一些问题。但与此同时，您可能会遇到不同的结果：

a = b = sys.float_info.max
print a + (a-b)/2 # prints a really big number
print (a+b)/2 # prints inf

相似地，

a = b = float("inf")
print a+(a-b)/2 # prints nan
print (a+b)/2 # prints inf

后一个例子是不同的，尽管我不清楚哪个更好。对于为什么会出现这种情况，您可以查看上面链接的文章中的溢出解释。