algorithm - 使用 mid=first+(last-first)/2 代替 (first+last)/2 的效果

Question

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

标签： algorithmbinary-search

Answer 1

如果使用mid = (first + last) / 2then 有可能在 first 或 last 为 时溢出MAX，即当 first 或 last 为最大值或范围时，再添加一个数字将溢出。

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

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