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 Zylinder wird üblicherweise am Ende des Wörterbuches begonnen, während die Suche nach Aal im vorderen Bereich begonnen werden dürfte.
Der Algorithmus Bearbeiten
Die Interpolationssuche geht von sortierten Daten aus. Sie eignet sich am besten für gleichverteilte Daten. 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.
Beispiel Bearbeiten
Gegeben ist ein Array :
| 2 | 4 | 7 | 9 | 12 | 21 | 26 | 31 | 37 |
In diesem Array soll der Wert gesucht werden.
Anfangs werden die linke und rechte Grenze auf die Grenzen des Arrays gesetzt, also und . Dann wird die Position des Teilungselements mit Hilfe der folgenden Formel berechnet:
In diesem Fall ergibt das (rot = Suchbereich, blau = x, fett = gesucht):
| 2 | 4 | 7 | 9 | 12 | 21 | 26 | 31 | 37 |
Daraufhin wird geschaut, ob das gefundene Element das gesuchte ist. Ist dies der Fall, wird abgebrochen, andernfalls wird der Suchbereich eingeschränkt. Wenn das zu klein gewählt ist – man also rechts suchen muss – wird die linke Grenze auf gesetzt und darin gesucht. Ansonsten ist das x zu groß, und man muss links suchen, die rechte Grenze wird daher auf gesetzt und jetzt im linken Bereich gesucht.
Da der Wert kleiner als das gesuchte Element ist, wird die linke Grenze auf gesetzt. Die rechte Grenze bleibt, und es ergibt sich folgende Formel:
Das Array sieht nun so aus:
| 2 | 4 | 7 | 9 | 12 | 21 | 26 | 31 | 37 |
Da nun ist, also das Element gefunden wurde, wird die Suche beendet. Sie hat 2 Schritte benötigt.
Komplexität Bearbeiten
Eine Untersuchung der Interpolationssuche erweist sich als sehr komplex, als Laufzeit kann jedoch (n ist die Anzahl der Elemente) im durchschnittlichen Fall angenommen werden. Im ungünstigsten Fall (die interpolierte erwartete Position ist immer am Rand) beträgt die Laufzeit allerdings . Diese Beeinträchtigung löst die Quadratische Binärsuche.
Beispielimplementierungen Bearbeiten
Delphi Bearbeiten
type TIntArray = array of integer; function interpolierteSuche(schluessel: integer; var daten: TIntArray): integer; var links, rechts, versch, aPos: integer; begin links := 0; rechts := high(daten); versch := 0; aPos := 0; while (schluessel >= daten[links]) and (schluessel <= daten[rechts]) do begin versch := daten[rechts] - daten[links]; aPos := links + round((rechts - links) * (schluessel - daten[links]) / versch); if (schluessel > daten[aPos]) then links := aPos + 1 else if (schluessel < daten[aPos]) then rechts := aPos - 1 else begin result := aPos; exit; end; end; result := - 1; end; Siehe auch Bearbeiten
Literatur Bearbeiten
- Robert Sedgewick: Algorithmen in C. Addison-Wesley, Bonn 1992, ISBN 3-89319-376-6, S. 239–241.
Einzelnachweise Bearbeiten
- Prof. Dr. Thomas Seidl, Dr. Marcus Gossler: Algorithmen und Datenstrukturen - Kapitel 4: Suchen. Hrsg.: Ludwig-Maximilians-Universität München - Lehrstuhl für Datenbanksysteme und Datamining. (lmu.de [PDF]).