在二进制搜索中，为什么 mid = (left + (right - left)) // 2 比 mid = (left + right) // 2 好？

Question

在二分查找 while 循环中：

left, right = 0, len(nums)
while left < right:
    mid = (left + right) // 2
    if nums[mid] == target:
        return mid

为什么在 python 以外的某些语言中 mid = (left + (right - left)) // 2 比 mid = (left + right) // 2 更好？

编辑：好像我把括号弄错了。感谢您指出这一点，它对我来说更清楚了。我会这样离开，以防其他人偶然发现这一点。我在 youtube 视频中看到了这个评论，但是那个人从来没有解释为什么一个会比另一个更好。谢谢大家的回答！

谢谢大家！

Answer 1

如果值对于它们的 int 表示而言太高，

这是 C 等语言中的一个问题，其中 int 变量有限制，但 Python 中没有。使用更直接的代码应该没问题。

Answer 2

好吧，你把括号弄错了。我会让你弄明白的。

但是要回答你的问题：

在 Python 中没关系，因为整数可以根据需要增长。

在其他语言中，整数的大小有限制，left + right 可能会溢出，而替代计算则不会。

Answer 3

在Python中，两者都不是更好。或者更确切地说，(left + right) // 2 稍微好一点，因为它少了一次算术运算。但这可以忽略不计。

在其他语言中，left + (right - left) // 2 用于避免 integer overflow，这可能在执行 left + right 时发生。这在 Python 中不会发生，因为 Python 本身允许任意大的整数；所以你看到的建议与 Python.

无关

Answer 4

这样做是为了处理C、C++等语言中数字和的溢出。您对整数范围有限制。在

                int mid = (low+high)/2;

我们先求和再除法，对于大的low和high值可能会溢出缓冲区。

这种溢出情况的处理方法是先计算差值，然后除以差值并加上低位。结果是，

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

In Binary search why doing mid = (left + (right - left)) // 2 is better than mid = (left + right) // 2?