Interpolationssuche
aus Wikipedia, der freien Enzyklopädie
Die Interpolationssuche, auch Intervallsuche genannt, ist ein von der binären Suche abgeleitetes Suchverfahren, das auf Listen und Feldern zum Einsatz kommt.
Während der Algorithmus der binären Suche stets das mittlere Element des Suchraums überprüft, versucht der Algorithmus der Interpolationssuche im Suchraum einen günstigeren Teilungspunkt als die Mitte zu erraten. Die Arbeitsweise ist mit der eines Menschen vergleichbar, der ein Wort in einem Wörterbuch sucht: Die Suche nach einem mit Z beginnenden Wort wird üblicherweise am Ende des Wörterbuches begonnen, während die Suche nach Aal im vorderen Bereich begonnen werden dürfte.
Inhaltsverzeichnis |
[Bearbeiten] Der Algorithmus
Die Interpolationssuche geht von sortierten und gleichverteilten Daten aus. Des Weiteren wird ein wahlfreier Zugriff auf die Elemente vorausgesetzt. Die Daten werden bei der Interpolationssuche in Abhängigkeit vom Schlüssel geteilt. Hat dieser einen großen Wert, befindet sich das gesuchte Element aufgrund der Vorsortierung im hinteren Teil der Daten. Dementsprechend wird auch im hinteren Teil der Daten die Teilung vorgenommen. Bei einem kleinen Schlüssel wird das Feld entsprechend im vorderen Teil gespalten.
Für alle Daten lässt sich die Teilungsposition berechnen, indem zunächst die Anzahl aller Elemente durch die Anzahl verschiedener Elemente dividiert wird, und anschließend mit dem gesuchten Schlüssel multipliziert wird:
Die Position des gesuchten Elementes wird somit interpoliert, indem die Gleichverteilung der Daten für eine Abbildung des Schlüssels auf die Liste bzw. das Feld genutzt wird.
Nun kann überprüft werden, ob der Schlüssel des teilenden Elementes einen größeren oder kleineren Wert als der Schlüssel des gesuchten Elementes hat. Bei identischen Schlüsseln ist die Suche bereits beendet. Wenn das teilende Element einen kleineren Wert hat, wird der rechte Teilbereich weiteruntersucht, andernfalls der linke Teilbereich. Die Zahl der Elemente sowie die Zahl der verschiedenen Schlüssel wird für den neuen Bereich ermittelt, und anschließend eine neue Teilungsposition interpoliert.
[Bearbeiten] Komplexität
Eine Untersuchung der Interpolationssuche erweist sich als sehr komplex, als Laufzeit kann jedoch O(log(log n)) (n ist die Anzahl der Elemente) im durchschnittlichen Fall angenommen werden. Im ungünstigsten (die interpolierte erwartete Position ist immer am Rand) Fall beträgt die Laufzeit allerdings O(n)). Diese Beeinträchtigung löst die Quadratische Binärsuche.
[Bearbeiten] Beispielimplementierungen
[Bearbeiten] Java
public int interpolierteSuche(int schlüssel, int daten[]) { int links = 0; // linke Teilfeldbegrenzung int rechts = daten.length - 1; // rechte Teilfeldbegrenzung int versch; // Anzahl verschiedener Elemente int pos; // aktuelle Teilungsposition // solange der Schlüssel im Bereich liegt (andernfalls ist das gesuchte // Element nicht vorhanden) while( schlüssel >= daten[links] && schlüssel <= daten[rechts] ){ // Aktualisierung der Anzahl der verschiedenen Elemente versch = daten[rechts] - daten[links]; // Berechnung der neuen interpolierten Teilungsposition pos = links + (int)(((double)rechts - links) * (schlüssel - daten[links]) / versch); if( schlüssel > daten[pos] ) // rechtes Teilintervall links = pos + 1; // daten[pos] bereits überprüft else if( schlüssel < daten[pos] ) // linkes Teilintervall rechts = pos - 1; // daten[pos] bereits überprüft else // Element gefunden return pos; // Position zurückgeben } return -1; // Element nicht gefunden }
[Bearbeiten] C
/** * Liefert 1 zurück, wenn X in M gefunden wurde, ansonsten 0. * Beim Aufruf wird als 4. Argument eine Variable per Adresse * übergeben, in die bei Erfolg die Position von X in M geschrieben wird. * @param const int[] M Feld, in dem gesucht werden soll * @param int n Groesse des Feldes * @param int X der gesuchte Eintrag * @param int * index Position des gesuchten Eintrags X in M * @return int 1=gefunden, 0=nicht gefunden */ int interpolation_search( const int M[], int n, int X, int *index ) { double dx, dy; double m; // Steigung double b; // Y-Achsenabschnitt int links = 0; // x1 int rechts = n-1; // x2 int pos; // vermutete Position if ( M==NULL || X < M[0] || X > M[n-1] ) { return 0; } while ( links <= rechts ) { dx = rechts - links; if ( dx == 1 ) { if ( M[rechts] == X ) { *index = rechts; return 1; } else if ( M[links] == X ) { *index = links; return 1; } return 0; } if ( dx == 0 ) // 0 Division vorbeugen { return 0; } dy = M[rechts] - M[links]; if ( dy == 0 ) // keine Steigung { if ( M[links] == X ) { *index = links; return 1; } else { return 0; } } m = dy / dx; // Steigung b = M[links] - ( m * links ); pos = ( X - b ) / m; // Vermutete Position berechnen if ( M[pos] == X ) { *index = pos; return 1; } else if ( M[pos] > X ) { rechts = pos - 1; } else { links = pos + 1; } } return 0; }
[Bearbeiten] Literatur
Robert Sedgewick: Algorithmen in C. Addison-Wesley, 1992, S. 239-241
[Bearbeiten] Weblinks
siehe auch: Intervallschachtelung