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  .[1] Diese Beeinträchtigung löst die Quadratische Binärsuche.

Beispielimplementierungen Bearbeiten

Delphi-Methode

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

  1. Thomas Seidl, Marcus Gossler: Algorithmen und Datenstrukturen - Kapitel 4: Suchen. Hrsg.: Ludwig-Maximilians-Universität München - Lehrstuhl für Datenbanksysteme und Datamining. (lmu.de [PDF]).