Interpolationssuche
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.
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.
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ächigung löst die Quadratische Binärsuche.
Beispielimplementierungen
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
}
/**
* 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;
}
Literatur
Robert Sedgewick: Algorithmen in C. Addison-Wesley, 1992, S. 239-241
Weblinks
siehe auch: Intervallschachtelung