c++ - 为什么 M = L + ((R - L)/2) 而不是 M=(L+R)/2 在 C++ 中避免溢出？

Question

你好，我正在查看“假设一个排序数组在你事先不知道的某个枢轴旋转。(即 0 1 2 4 5 6 7 可能变成 4 5 6 7 0 1 2)”这个问题的 C++ 解决方案。你如何有效地在旋转数组中找到一个元素？你可以假设数组中不存在重复项。”

int rotated_binary_search(int A[], int N, int key) {
    int L = 0;
    int R = N - 1;

    while (L <= R) {
    // Avoid overflow, same as M=(L+R)/2
        int M = L + ((R - L) / 2);
        if (A[M] == key) return M;

    // the bottom half is sorted
        if (A[L] <= A[M]) {
            if (A[L] <= key && key < A[M])
                R = M - 1;
            else
                L = M + 1;
        }
    // the upper half is sorted
        else {
            if (A[M] < key && key <= A[R])
                L = M + 1;
            else 
                R = M - 1;
        }
    }
    return -1;
}

看到评论说使用 M = L + ((R - L)/2) 而不是 M=(L+R)/2 避免溢出。这是为什么？提前致谢

Answer 1

因为它确实...

让我们暂时假设您正在使用无符号字符(当然这同样适用于更大的整数)。

如果 L 为 100，R 为 200，则第一个版本为:

M = (100 + 200) / 2 = 300 / 2 = 22

100+200溢出(因为最大的unsigned char是255)，得到100+200=44(unsigned no.加法)。

另一方面，第二个:

M = 100 + (200-100) / 2 = 100 + 100 / 2 = 150

没有溢出。

正如@user2357112 在评论中指出的那样，天下没有免费的午餐。如果 L 为负，则第二个版本可能无法工作，而第一个版本可以。