两个整数的中值

Question

6

什么是以下技术之间的区别：

int x = (right + left) / 2;

并且

int x = left + (right - left) / 2;

在进行二分查找时，我在第一种情况下遇到了时间限制异常，在第二种情况下得到了通过的结果。

- Madi Sagimbekov

2

在第一种情况下，如果左右两边太大，则可能会发生整数溢出，这就是为什么应该使用第二种变体的原因。 - Evgeniy Strepetov

好的，谢谢，我现在明白了。 - Madi Sagimbekov

@MadiSagimbekov 只是一个建议，尝试通过检查每次迭代中变量的值来自己调试这些小错误。 - Daga

这是一个 OJ 问题，我不知道测试用例是什么。当 n = Integer.MAX_VALUE 且搜索元素接近 Integer.MAX_VALUE 时，可能会出现 TLE。 - Madi Sagimbekov

2个回答

2

整数的上限（边界）是2,147,483,647。

您的right+left值超出了int的边界。
但是left + (right - left) / 2的值小于int的边界，所以第二个表达式能正常工作。

如果要相加如此大的数字，请使用long。

- Azat Nugusbayev

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tayyab Kazmi · Accepted Answer

您的int变量之和

right + left（超出整数限制）

过大并超过了整数存储限制，这就是由于求和而导致溢出的原因，但当您使用差值版本时，第二个

left +（right-left）（在整数限制范围内）

更适合计算，并有利于机器。