这两个公式有什么区别
mid = low + (high - low) / 2;
mid = (high + low) / 2;
最佳答案
在第二版中,如果high + low
大于int
的最大值(假设high
是int
),则它可能会溢出,从而引发未定义的行为。第一个版本解决了该特定错误。
第一个版本仍然存在问题,例如如果low
是一个非常大的负数,则该差值仍会溢出。
从c++ 20开始,您应该为此使用 std::midpoint
,它可以处理大量的极端情况,并为所有情况做正确的事情。
这个看似简单的功能实际上很难实现,实际上,Marshall Clow在cppcon 2019上给出了一个小时的talk,其中涵盖了该功能的实现。
关于c++ - 二进制搜索: how to determine half of the array,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63847183/