在C中安全二进制搜索

从理论上讲,大多数二进制搜索算法的实现都被打破了,因为程序可能会遇到大型数组的分段错误.例如,以下实现就是这种情况.

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);
}

我的问题是,二进制搜索算法的实现的安全版本将如何？

代码中有问题的部分是它的中点计算:

m = (l + h) / 2;

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

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

有关详细信息,请参见二进制搜索 - 算术.