从理论上讲,大多数二分搜索算法的实现都是错误的,因为程序可能会遇到大型数组的段错误。例如,以下实现就是这种情况。
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;
参见 Binary Search - Arithmetic了解详情。
关于c - C 中的安全二进制搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34093386/