Interpolationssuche

Die Interpolationssuche, auch Intervallsuche genannt, ist ein von der Binären Suche abgeleitetes Suchverfahren, das auf Strukturen mit wahlfreiem Zugriff wie z. B. Listen und Arrays zum Einsatz kommt. Das Verfahren geht davon aus, dass die Daten aufsteigend sortiert und möglichst gleichverteilt sind.

Während der Algorithmus der Binären Suche stets das mittlere Element des Suchraums überprüft und ihn somit in jedem Schritt halbiert, versucht der Algorithmus der Interpolationssuche einen günstigeren, dem Suchwert nahe liegenden Teilungspunkt zu finden. Dabei adaptiert er die intuitive Vorgehensweise der Suche nach einem Wort in einem Wörterbuch: Die Suche nach Wolf vermutet den Treffer nicht nur in der 2. Hälfte (wie beim Binären Suchen), sondern im hinteren Teil des Wörterbuches, während die Suche nach Boot weit vorne beginnt.

Der Algorithmus

In einer Schleife oder durch rekursive Aufrufe bestimmt der Algorithmus im anfänglichen bzw. verbliebenen Suchraum anhand des Suchbegriffes eine Teilungsposition. Die Bestimmung der Teilungsposition erfolgt durch Ausnutzung der Gleichverteilung der Daten und nach Bereinigung des Suchbegriffs um den Basiswert (= kleinster Wert).

${\text{Position}}:={\frac {\text{Anzahl der Werte im Suchraum}}{{\text{größter Wert}}-{\text{kleinster Wert}}}}\cdot ({\text{gesuchter Wert}}-{\text{kleinster Wert}})$

Ist der Datenwert an dieser Position identisch mit dem Suchbegriff, terminiert der Algorithmus. Ist der Datenwert kleiner, befindet sich der gesuchte Wert aufgrund der Vorsortierung im hinteren Teil der Daten. In diesem Fall wird der Suchraum verkürzt, indem die linke Grenze auf die gefundene Position verschoben und die rechte Grenze beibehalten wird. Ist der Datenwert größer, erfolgt die Verkürzung zum vorderen Teil der Daten durch Verschieben der rechten Grenze auf die gefundene Position und Beibehaltung der linken Grenze.

Sodann folgt der nächste Schleifendurchlauf bzw. rekursive Aufruf.

Beispiel

Gegeben ist ein Array $A$, in dem der Wert $w=7$ gesucht werden soll.

2

4

7

9

12

21

26

31

37

Die Position $p$ des Teilungselements ergibt sich im allgemeinen Fall aller Schleifendurchläufe durch Anpassung obiger Formel an den jeweils verbliebenen Suchraum

$p:=l {\frac {r-l}{A[r]-A[l]}}\cdot (w-A[l])$

mit anschließendem Runden auf den nächsten ganzzahligen Wert.

1. Schleifendurchlauf

Anfangs werden die linke und rechte Grenze auf die Grenzen des Arrays gesetzt, also $l:=0$ und $r:=8$. Der erste Schleifendurchlauf ergibt (rot = Suchbereich, blau = $A[p]$, fett = gesucht):

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

2

4

7

9

12

21

26

31

37

Daraufhin wird geschaut, ob das gefundene Element das gesuchte ist. Das ist nicht der Fall. Der Wert $A[p]=A[1]=4$ ist kleiner als das gesuchte Element $w=7$. Somit muss auf der rechten Seite weiter gesucht werden. Hierzu wird die linke Grenze auf $l:=p 1=2$ erhöht und die rechte Grenze beibehalten.

2. Schleifendurchlauf

Der zweite Schleifendurchlauf berechnet:

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

2

4

7

9

12

21

26

31

37

Nun ist $A[p]=A[2]=7=w$. Das Element wurde gefunden und die Suche endet. Sie hat 2 Schritte benötigt.

Komplexität

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

Beispielimplementierungen

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

• Intervallschachtelung
• Komplexitätstheorie
• Landau-Symbole

Literatur

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