Неожиданный результат в C-алгебре для алгоритма поиска

Question

Я реализовал этот алгоритм поиска для упорядоченного массива целых чисел. Он отлично работает для первого набора данных, который я передаю (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

Thankyou!

Рис

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)));

Как указал Навин, вам также необходимо убедиться, что фактические расчеты выполнены с такой точностью. Это может быть сделано путем наложения.

Answer 2

m = 0 + ((68816 - 0) * (100000 - 0)) / (114836 - 0);

68816 * 100000 = 6881600000 = (binary)110011010001011001110001000000000

Это 33 бита. Практически на всех платформах int имеют 32 бита или (в более редких случаях) 16 бит.

Вы можете попробовать использовать long long, который гарантированно будет не менее 64 бит (добавлен в C99, но большинство компиляторов также поддерживают его в C90).

Answer 3

Ваша арифметика, вероятно, превышает размер int на вашей платформе.

Вам нужно сделать одну из двух вещей. Либо используйте более широкий целочисленный тип (если имеется), либо измените ваши вычисления, чтобы вам не нужно было создавать такое большое промежуточное значение.

Answer 4

Чтобы избежать таких проблем, как переполнение данных, вы можете дополнительно использовать библиотеку больших чисел. Хороший пример: http://gmplib.org/. Конечно, это добавит немного больше накладных расходов, но общая производительность очень хорошая.

Answer 5

Это потому, что промежуточное значение вычисления (68816 - 0) * (100000 - 0) превышает значение, которое может храниться в int. Вы можете привести промежуточное значение к типу данных, который может содержать большее число (например, long long), чтобы решить проблему

Answer 6

Вы должны быть осторожны с целочисленным переполнением. Было бы лучше выполнить вычисление m как тип, больший, чем int, а затем вернуть обратно к int, когда вы закончите.

Кроме того, вам может потребоваться быть осторожным, если ваш набор содержит дубликаты, поскольку вы можете получить ошибку деления на ноль в той же строке (т. Е. Когда set[r] == set[l]).