Interpolationssuche

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: ${\displaystyle {\text{Position}}={\frac {\text{Anzahl der Elemente}}{\text{Anzahl verschiedener Elemente}}}\cdot {\text{gesuchter Wert}}}$

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.

Gegeben ist ein Array ${\displaystyle A}$:

In diesem Array soll der Wert ${\displaystyle w:=7}$ gesucht werden.

Anfangs werden die linke und rechte Grenze auf die Grenzen des Arrays gesetzt, also ${\displaystyle l:=0}$ und ${\displaystyle r:=8}$. Dann wird die Position ${\displaystyle p}$ des Teilungselements mit Hilfe der folgenden Formel berechnet: ${\displaystyle p:=l+{\frac {w-A[l]}{A[r]-A[l]}}\cdot (r-l)}$

In diesem Fall ergibt das (rot = Suchbereich, blau = x, fett = gesucht):

${\displaystyle p:=0+{\frac {7-2}{37-2}}\cdot (8-0)=1{\frac {1}{7}}\to 1}$

Daraufhin wird geschaut, ob das gefundene Element das gesuchte ist. Ist dies der Fall, wird abgebrochen, andernfalls wird der Suchbereich eingeschränkt. Wenn das ${\displaystyle p}$ zu klein gewählt ist – man also rechts suchen muss – wird die linke Grenze auf ${\displaystyle p+1}$ gesetzt und darin gesucht. Ansonsten ist das x zu groß, und man muss links suchen, die rechte Grenze wird daher auf ${\displaystyle p-1}$ gesetzt und jetzt im linken Bereich gesucht.

Da der Wert ${\displaystyle A[1]=4}$ kleiner als das gesuchte Element ist, wird die linke Grenze auf ${\displaystyle l:=p+1=2}$ gesetzt. Die rechte Grenze bleibt, und es ergibt sich folgende Formel:

${\displaystyle p:=2+{\frac {7-7}{37-7}}\cdot (8-2)=2\to 2}$

Das Array sieht nun so aus:

Da nun ${\displaystyle A[x]=A[2]=7=w}$ ist, also das Element gefunden wurde, wird die Suche beendet. Sie hat 2 Schritte benötigt.

Eine Untersuchung der Interpolationssuche erweist sich als sehr komplex, als Laufzeit kann jedoch ${\displaystyle {\mathcal {O}}(\log(\log(n)))}$ (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 ${\displaystyle {\mathcal {O}}(n)}$.[1] Diese Beeinträchtigung löst die Quadratische Binärsuche.

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;

• Intervallschachtelung
• Komplexitätstheorie
• Landau-Symbole

• Robert Sedgewick: Algorithmen in C. Addison-Wesley, Bonn 1992, ISBN 3-89319-376-6, S. 239–241.

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]).