搜索算法的C代数意外结果

Question

我已经为有序的整数数组实现了这个搜索算法.它适用于我提供的第一个数据集(500个整数),但在较长的搜索时失败.但是,所有这些集合都与我为分配实现的其他四种搜索算法完美配合.

这是在第178行返回seg故障的函数(由于意外的负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 }

OUTPUT:

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

谢谢!

里斯

Answer 1

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指出的那样,您还需要确保以这种精度进行实际计算.这可以通过铸造来完成.