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

Question

您好我正在查看问题的C++解决方案"假设一个排序的数组在事先未知的某个轴上旋转.(即,0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2).你好.有效地在旋转的数组中找到一个元素？你可以假设数组中没有重复."

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溢出(因为最大的无符号字符是255),你得到100 + 200 = 44(无符号否.).

第二,另一方面:

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

没有溢出.

正如@ user2357112在评论中指出的那样,没有免费的午餐.如果L为负数,则第一个版本可能不起作用.