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

Question

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

Answer 1

如果使用 mid = (first + last)/2 那么当 first 或 last 为 MAX 时，即有可能发生溢出，即当 first 或 last 是maximum or range，再加一个数就会溢出。

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

此外，由于在竞争性编程测试用例中会测试您的代码以适应极端情况，因此很可能其中一个测试用例具有这些最大范围数。所以建议使用 mid = first + (last-first)/2