这个插值搜索实现有什么问题？

这是在Internet上找到的插值搜索算法的常见C / C ++实现。 但是，当与大约100000个整数的排序数组一起使用时，中间变量开始生成负数组索引，从而导致分段错误。 问题是什么？

#include  #include  #include  int interpolationSearch(int sortedArray[], int toFind, int len) { // Returns index of toFind in sortedArray, or -1 if not found int low = 0; int high = len - 1; int mid; while (sortedArray[low] = toFind) { mid = low + ((toFind - sortedArray[low]) * (high - low)) / (sortedArray[high] - sortedArray[low]); if (sortedArray[mid]  toFind) { high = mid - 1; } else { return mid; } } if (sortedArray[low] == toFind) return low; else return -1; // Not found } int main(void) { srand(time(0)); int arr[100000]; for (int i=0; i<100000; i++) { arr[i] = rand()%100000; } int length = sizeof(arr)/sizeof(int); qsort(arr,length,sizeof(int),order); for (int j=0; j<10000; j++) { interpolationSearch(arr,rand()%100000,length); } } 

Answer 1

子表达式： ((toFind - sortedArray[low]) * (high - low))

…可以轻松评估为： ((99999-0) * (99999-0)) == 99999^2

…比2 ^ 31（== 32位有符号整数的范围）大得多。

一旦超过2 ^ 31-1，整数将溢出为负数，因此您的负指数。 如果它超过2 ^ 32（它也可以做到），那么（很可能在技术上未定义）你将失去高阶位，你最终会得到有效的随机偏移，包括正负。

为避免所有这些，您需要仔细进行数学运算，以确保没有任何子表达式产生整数溢出。 通常，最简单的方法是转换为浮点，其范围比32位整数大许多个数量级。

在最后的分析中，对于二进制搜索这样的插值通常是不值得的 – 计算插值的费用通常大于它“保存”的循环的少量额外迭代。

Answer 2

正如其他答案所解释的那样，您正在尝试计算表单的表达式

 A * B / C 

但这是错误的，因为A * B溢出。 修改表达式的建议

 A * (B / C) 

不起作用，因为通常B小于C ，因此整数除法将截断为零。

切换到浮点的建议会起作用，但成本会很高。 但是你可以通过将表达式转换为：

 A * ((B * F) / C) / F 

（其中F是精心挑选的2的幂）。

Answer 3

问题在于计算mid的表达式。 即使使用32位整数，该产品也很容易溢出。 然后它变成消极的。 在产品之前进行分割可能会更好。

将中间计算更改为使用64位整数（至少用于中间计算）可以解决问题。

下面是我的修改版本（int64_t在定义：

 int interpolationSearch(int sortedArray[], int toFind, int len) { // Returns index of toFind in sortedArray, or -1 if not found int low = 0; int high = len - 1; int mid; int l = sortedArray[low]; int h = sortedArray[high]; while (l <= toFind && h >= toFind) { int64_t high_low = (high - low); int64_t toFind_l = (toFind - l); int64_t product = high_low*toFind_l; int64_t h_l = hl; int64_t step = product / h_l; mid = low + step; /* mid = (low + high)/2;*/ int m = sortedArray[mid]; if (m < toFind) { l = sortedArray[low = mid + 1]; } else if (m > toFind) { h = sortedArray[high = mid - 1]; } else { return mid; } } if (sortedArray[low] == toFind) return low; else return -1; // Not found } 

更简单的解决方法是通过使用： mid = (low + high) / 2使其成为二分法搜索而不是插值。 即使它收敛比插值稍慢，它也避免了包括产品和除法在内的多个操作，从而使内循环更快。 不确定插值的潜在更快收敛可以弥补简单性的损失。

我做了一些性能测试。 我的测试程序的来源包含在这个问题中

令人惊讶的是（对我来说）使用浮点数提供了比使用大整数更有效的程序。 在我的系统中，二进制搜索在数组中大约1000个项目变得更快。 对于大小为100000的数组，插值搜索比简单二进制搜索快近两倍。