使用 mid=first+(last-first)/2 而不是 (first+last)/2 的效果

Question

为什么人们使用mid=first+(last-first(/2而不是(first+last(/2，在二叉搜索的情况下( 两者之间有区别吗？如果有，请告诉我，因为我无法理解其中的区别。

Answer 1

如果你使用mid = (first + last) / 2那么当第一个或最后一个MAX时，就有可能溢出，即当第一个或最后一个是最大值或范围时，再添加一个数字就会溢出。

所以我们使用mid = first + (last-first) / 2，因为即使第一个或最后一个是最大范围，它也不会溢出。

此外，正如在竞争性编程测试用例中所做的那样，它将在极端情况下测试您的代码，因此其中一个测试用例很可能具有这些最大范围数。因此，建议使用mid = first + (last-first)/2

Answer 2

是的，例如在Java和C++中，如果hi + lo变得太大，后者((hi + lo) / 2(可能会抛出异常。在 Python 和 JavaScript 中，这可能没问题。

这里似乎有更多关于这方面的信息。

参考

在二叉搜索中计算中间

Answer 3

如果first+last < Maximum_value_for_a_variable，两者都会给出相同的结果。 因此，使用mid=first+(last-first)/2避免溢出要安全得多。 让我们假设 first、last 和 mid 是 int 变量。

int mid; 
int first = 50010;
int last = 2147483275;
//Maximum value for a variable of type int is 2147483647
(first+last)/2 //-1073717005 overflow because first+last > integer maximum value
first+(last-first)/2 //1073766642 no overflow

Answer 4

在大多数编程语言中，数据类型都有限制。因此，如果我们使用(first+last)/2那么添加第一个和最后一个可能会超过给定的限制，并且会产生运行时错误。

为避免这种情况，建议使用first + (last-first)/2.与极端情况一样，它也不会超过其数据类型的限制。