1

我已经为一个有序的整数数组实现了这个搜索算法。它适用于我提供的第一个数据集（500 个整数），但在更长的搜索中失败。但是，所有这些集合都与我为该作业实施的其他四种搜索算法完美配合。

这是在第 178 行返回段错误的函数（由于意外的负 m 值）。任何帮助将不胜感激。

代码：

155 /* perform Algortihm 'InterPolationSearch' on the set
156  * and if 'key' is found in the set return it's index
157  * otherwise return -1 */
158 int
159 interpolation_search(int *set, int len, int key)
160 {
161   int l = 0;
162   int r = len - 1;
163   int m;
164
165   while (set[l] < key &&  set[r] >= key)
166   {
167
168     printf ("m = l + ((key - set[l]) * (r - l)) / (set[r] - set[l])\n");
169
170     printf ("m = %d + ((%d - %d) * (%d - %d)) / (%d - %d);\n", l, key, set[l], r, l, set[r], set[l]);
171     m = l + ((key - set[l]) * (r - l)) / (set[r] - set[l]);
172     printf ("m = %d\n", m);
173
174 #ifdef COUNT_COMPARES
175     g_compares++;
176 #endif
177
178     if (set[m] < key)
179       l = m + 1;
180     else if (set[m] > key)
181       r = m - 1;
182     else
183       return m;
184   }
185
186   if (set[l] == key)
187     return l;
188   else
189     return -1;
190 }

输出：

m = l + ((key - set[l]) * (r - l)) / (set[r] - set[l])
m = 0 + ((68816 - 0) * (100000 - 0)) / (114836 - 0);
m = -14876

谢谢！

里斯

4

6 回答 6

5

68816 * 100000 大于 2^31，这很可能是你机器int数据类型的限制。您遇到整数溢出。

如果您的编译器支持它，请尝试更改为long long. 您可以通过运行检查

#include <stdlib.h>
printf("the long long type is %u bits", (unsigned int) (CHAR_BIT * sizeof (long long)));

正如 Naveen 指出的那样，您还需要确保以这种精度进行实际计算。这可以通过铸造来完成。

于 2010-03-31T07:20:10.937 回答
1

您的算法可能超出了int您平台上的大小。

你需要做两件事之一。要么使用更宽的整数类型（如果可用），要么重新计算你的计算，这样你就不需要创建如此大的中间值。

于 2010-03-31T07:19:40.877 回答
1 
m = 0 + ((68816 - 0) * (100000 - 0)) / (114836 - 0);

68816 * 100000 = 6881600000 = (binary)110011010001011001110001000000000

那是 33 位。在几乎所有平台上int都是 32 位或（在极少数情况下）16 位。

您可以尝试使用long long保证至少 64 位（在 C99 中添加，但大多数编译器在 C90 中也支持它）。

于 2010-03-31T07:21:33.160 回答
0

您需要小心整数溢出。最好将 的 计算m为大于 的类型int，然后在完成时再转换回int。

此外，如果您的集合包含重复项，您可能需要小心，因为您可能会在同一行出现除以零错误（即 when set[r] == set[l]）。

于 2010-03-31T07:21:19.517 回答
0

这是因为计算的中间值(68816 - 0) * (100000 - 0)超过了可以保存在int. 您可以将中间值转换为可以容纳更大数字的数据类型（例如 a long long）来解决问题

于 2010-03-31T07:21:51.077 回答
0

为避免数据溢出等问题，您还可以使用大数字库。一个很好的例子是： http: //gmplib.org/。当然会增加一点开销，但是整体性能还是很不错的。

于 2010-03-31T07:28:14.050 回答