使用 l+(r-l)/2 避免溢出

Avoiding Overflow using l+(r-l)/2

当我学习合并排序实现时，我遇到了下面的代码：

// Same as (l+r)/2, but avoids overflow for 
// large l and h 
int m = l+(r-l)/2;

  1. (l+r)/2 和 l+(r-l)/2 有什么区别？后者计算为 r/2.

  2. (l+r)/2怎么会溢出，l+(r-l)/2怎么解决？

  3. h是什么？ （我认为这是一个错字，应该是 r）

  1. 请再次检查 - 它扩展为 l + r/2 - l/2 即 l/2 + r/2。请注意，我们不能只使用 l/2 + r/2，因为会有整数截断，因此 3/2 + 5/2 = 1 + 2 = 3，但所需的值为 4。

  2. 假设l和r都是int.

    3. 类型的正值

如果我们有：

int l = INT_MAX - 2;
int r = INT_MAX;

那么l + r部分就是INT_MAX - 2 + INT_MAX，这是整数溢出。 INT_MAX - 2 + (INT_MAX - (INT_MAX - 2))/2 没有整数溢出，因为每个子表达式都保留在 INT_MIN 和 INT_MAX 之间。

  1. 是的，打错了！