为什么我们使用中=低+ (最高–最低)/2;但不是中 = (低/2) +(高 /2)？
在二分查找中，我们使用 mid = low + (high – low)/2 而不是 (low + high)/2 来避免溢出，但是无法计算low/2和high/2分别然后相加而不是low+((high-low)/2)？
PS 如果 low + (high – low)/2 效率更高，那么为什么会这样呢？
In binary search, we use mid = low + (high – low)/2 instead of (low + high)/2 to avoid overflow, however, can't calculate low/2 and high/2 separately and then sum them up rather than low+(( high-low)/2)?
P.S. If low + (high – low)/2 is more efficient, then why is it so?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
假设 low 和 high 都是 3；那么 middle = 3/2 + 3/2 = 1+1 = 2，这实际上是相当糟糕的。 :-)
我们不使用 middle=high/2+low/2 的原因是它给了我们错误的结果
Let's say both low and high are 3; then middle = 3/2 + 3/2 = 1+1 = 2, which actually is quite bad. :-)
The reason we don't use middle=high/2+low/2 is that it gives us the wrong result
如果执行(low + high)/2，则当low和high为大整数时，有可能出现整数溢出。这可能会导致不正确的结果或未定义的行为。通过先从高位减去低位，我们可以防止溢出，因为差异可能会更小。
假设 low = 2,147,483,640，high = 2,147,483,645（正好低于 32 位有符号整数的最大值，即 2,147,483,647）。
如果我们直接使用表达式(low + high)/2，它看起来像这样：
这个结果看起来是正确的。但是，让我们看看当 low 和 high 增加 6 时会发生什么：
假设 low = 2,147,483,646，high = 2,147,483,651。
如果我们使用相同的表达式 (low + high)/2，则会是：
现在，4294967297 超出了 32 位有符号整数可以存储的最大值，导致整数溢出。这会导致未定义的行为。我们不会得到预期的中点值。
使用 (high - low)/2 计算中点有助于防止这种溢出，因为高点和低点之间的差异要小得多
If you do (low + high)/2, there is a possibility of integer overflow when low and high are large integers. This can lead to incorrect results or undefined behavior. By subtracting low from high first, we prevent overflow since the difference is likely to be smaller.
Suppose low = 2,147,483,640 and high = 2,147,483,645 (just below the maximum value of a 32-bit signed integer, which is 2,147,483,647).
If we use the expression (low + high)/2 directly, it would look like this:
This result seems correct. However, let's see what happens when low and high are increased by 6:
Suppose low = 2,147,483,646 and high = 2,147,483,651.
If we use the same expression (low + high)/2, it would be:
Now, 4294967297 exceeds the maximum value that can be stored in a 32-bit signed integer, causing an integer overflow. This results in undefined behavior. We won't get the expected midpoint value.
using (high - low)/2 to calculate the midpoint helps prevent such overflow because the difference between high and low is much smaller
当然。
对于很多硬件来说，除法比加减法慢，因此除法两次可能比使用更多加减法的方法慢。
Sure.
For a lot of hardware dividing is slower than adding and subtracting, so dividing twice might be slower than the method that uses more adding and subtracting.