c - 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;

参见 Binary Search - Arithmetic了解详情。