c++ - 二进制搜索: how to determine half of the array

Question

这两个公式有什么区别

mid = low + (high - low) / 2;


mid = (high + low) / 2;

Answer 1

在第二版中，如果high + low大于int的最大值(假设high是int)，则它可能会溢出，从而引发未定义的行为。第一个版本解决了该特定错误。
第一个版本仍然存在问题，例如如果low是一个非常大的负数，则该差值仍会溢出。
从c++ 20开始，您应该为此使用 std::midpoint ，它可以处理大量的极端情况，并为所有情况做正确的事情。
这个看似简单的功能实际上很难实现，实际上，Marshall Clow在cppcon 2019上给出了一个小时的talk，其中涵盖了该功能的实现。