C中的安全二进制搜索

Question

从理论上讲，大多数二进制搜索算法的实现都是中断的，因为程序可能会遇到大数组的分割错误。例如，下面的实现就是这样的。

int binarysearch(int x, int *v, int n) {
    int l, h, m;
    l = 0;
    h = n - 1;

    while (l <= h) {
        m = (l + h) / 2;

        if (x < v[m]) h = m - 1;
        else if (x > v[m]) l = m + 1;
        else return m;
    }

    return -1;
}

int main (void) 
{
    int n = (INT_MAX/4) * 3;
    int *v = calloc(n, sizeof(int));
    (void) binarysearch(1, v, n);
    cfree(v);
}

我的问题是，一个安全版本的二进制搜索算法的实现会是什么样子？

Answer 1

代码中有问题的部分是其中点计算：

m = (l + h) / 2;

将在int溢出时产生错误的结果。可以通过切换到long long计算或使用安全公式来避免这种情况：

m = (h - l)/2 + l;

详情请参见https://en.wikipedia.org/wiki/Binary_search_algorithm#Arithmetic。

Answer 2

指出错误发生的位置将是有帮助的--即，如果m = (l + h) / 2;溢出正整数的范围，那么l + h的计算就会失败。在这种情况下，答案将变为负数，有符号整数除法将传播符号位，产生一个较小的负数，当它用作数组索引时，它被解释为一个非常大的无符号正数。

我不记得我在哪里看到它，但有一个可爱的技巧，可以让你安全地计算平均2个数字，即使他们的总和超过机器的精度。本质上，给定任意两个数字a和b，请注意

a = (a & b) | (a & ~b)   # Each bit in a is either shared with b, or not
  = (a & b) + (a & ~b)   # Since these two terms share no bits
b = (a & b) | (b & ~a)
  = (a & b) + (b & ~a)   # Likewise

所以

(a + b) / 2 = [  (a & b) + (a & ~b) + (a & b) + (b & ~a) ] / 2
            = [2*(a & b) + (a & ~b) + (b & ~a)] / 2
            = [2*(a & b)] / 2 + [(a & ~b) + (b & ~a)] / 2
            = (a & b) + [(a & ~b) + (b & ~a)] / 2

最后，请注意，RHS上的(a & ~b) + (b & ~a)表达式只是a或b中的每一点，但两者都不是-- IOW，它是a ^ b。所以我们有

(a + b) / 2 = (a & b) + (a ^ b) / 2

没有溢出的可能。