Hi,
I've implemented this search algorithm for an ordered array of integers. It works fine for the first data set I feed it (500 integers), but fails on longer searches. However, all of the sets work perfectly with the other four search algorithms I've implemented for the assignment.
This is the function that returns a seg fault on line 178 (due to an unexpected negative m value). Any help would be greatly appreciated.
CODE:
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
Thankyou!
Rhys
