Unerwartetes Ergebnis in C Algebra für Suchalgorithmus

Question

habe ich diesen Suchalgorithmus für eine geordnete Array von ganzen Zahlen implementiert. Es funktioniert gut für die erste Datensatz ich es füttern (500 ganze Zahlen), aber nicht auf mehr sucht. Doch alle Sätze arbeiten perfekt mit den anderen vier Suchalgorithmen I für die Zuordnung implementiert haben.

Dies ist die Funktion, dass die Rendite einer seg Fehler auf der Leitung 178 (aufgrund eines unerwarteten negativen m-Wert). Jede Hilfe wäre sehr geschätzt.

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

Danke!

Rhys

Answer 1

Das ist, weil der Zwischenwert des calcualtion (68816 - 0) * (100000 - 0) den Wert übersteigt, der innerhalb eines int gehalten werden kann. Sie können den Zwischenwert auf einen Datentyp gegossen, die die größere Zahl (zum Beispiel eines long long) halten können, um das Problem zu lösen

Answer 2

68816 * 100000 mehr als 2 ^ 31, was sehr wahrscheinlich ist die Grenze Ihrer Maschine int Datentypen. Sie erleben Integer-Überlauf.

Wenn Ihr Compiler unterstützt, versucht Wechsel zu long long. Sie können, indem Sie überprüfen

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

Wie Naveen wies darauf hin, werden Sie auch sicher, dass die tatsächlichen Berechnungen vornehmen müssen in dieser Präzision hergestellt werden. Dies kann durch Gießen erfolgen.

Answer 3

Ihre Arithmetik ist wahrscheinlich die Größe von int auf Ihrer Plattform überfüllt.

Sie müssen eine von zwei Dinge zu tun. Verwenden Sie entweder einen größeren Integer-Typen (falls vorhanden) oder Neufassung Ihre Berechnung, so dass Sie nicht einen so großen Zwischenwert zu schaffen brauchen.

Answer 4

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

68816 * 100000 = 6881600000 = (binary)110011010001011001110001000000000

Das ist, 33 Bits. Auf nahezu allen Plattformen int sind 32 Bits oder (in selteneren Fällen) 16 Bit.

Sie können mit long long versuchen, die garantiert mindestens 64 Bit (hinzugefügt in C99, aber die meisten Compiler es in C90 unterstützt auch).

Answer 5

Sie müssen vorsichtig von Integer-Überlauf sein. Es wäre besser, die Berechnung von m als Typ als int größer auszuführen, und dann zurück zu int werfen, wenn Sie fertig sind.

Darüber hinaus können Sie müssen vorsichtig sein, wenn Ihr Satz Duplikate enthält, wie Sie eine Division durch Null-Fehler auf der gleichen Linie erhalten können (das heißt, wenn set[r] == set[l]).

Answer 6

Um Probleme wie Datenüberlauf zu vermeiden, können Sie zusätzlich eine große Zahl Bibliothek verwenden. Ein gutes Beispiel ist: http://gmplib.org/ . Natürlich wird es ein wenig mehr Aufwand, aber die Gesamtleistung ist sehr gut hinzufügen.