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

发布时间：2020-12-16 04:53:39 所属栏目：百科来源：网络整理

导读：您好我正在查看问题的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

您好我正在查看问题的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避免溢出.这是为什么？先生

解决方法

因为它确实……

让我们假设你使用无符号字符一分钟(当然也适用于更大的整数).

如果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为负数,则第一个版本可能不起作用.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!