12.5 Interpolationssuche

Grundidee

Wenn die Zahlen bzw. Elemente in dem Hauptarray einigermaßen gleichmäßig verteilt sind, benötigt man keinen Index-Array. Man kann versuchen, die Einstiegsposition für die Suche zu berechnen, zu interpolieren. Daher wird dieses Suchverfahren auch als Interpolationssuche bezeichnet.

50 sehr gleichmäßig verteilte Zahlen
Autor: Ulrich Helmich 2019, Lizenz: ---

Wir wollen hier nun nach vier dieser Zahlen suchen und wieder die durchschnittliche Suchzeit berechnen.

In dem Array befinden sich 50 Zahlen im Bereich zwischen 1 und 100. Wenn diese Zahlen einigermaßen gleichmäßig verteilt sind, kann man die Einstiegsposition für die Suche mit S/2 berechnen, wobei S die Suchzahl ist.

Wir wollen einmal die Zahl 50 suchen. Der Einstiegsindex ist dann 25. An der Position 25 finden wir die Zahl 52. Diese Zahl ist größer als die Suchzahl 50. Also suchen wir nach links weiter. Die erste Zahl, auf die wir stoßen, ist die 50, also die Suchzahl. Wir haben also 2 Vergleiche benötigt, um die 50 zu finden.

Die Zahl 61 ist wahrscheinlich ab Index 30 zu finden. Und dort ist sie auch, das heißt, wir haben nur 1 Vergleich benötigt, um die 61 zu finden.

Die Zahl 78 ist wahrscheinlich ab Index 39 zu finden. Dort steht die 79. Also suchen wir links weiter und finden sofort die 78. Auch hier haben wir nur 2 Vergleiche benötigt.

Auch die Zahl 94 finden wir nach 2 Vergleichen.

Die durchschnittliche Suchzeit für diese vier Zahlen liegt also unter 2,0. Eine solche Interpolationssuche ist also sehr effektiv, und man spart sich den Index-Array. Allerdings funktioniert die Interpolationssuche nur dann, wenn man die Einstiegsposition für die Suche auch tatsächlich einigermaßen zuverlässig berechnen kann. Dazu müssen die Elemente ziemlich gleichmäßig verteilt sein. Bei einer ungleichmäßigen Verteilung hilft dann aber immer noch die Indexsuche, die weiter oben erklärt wurde.

Umsetzung der Interpolationssuche

Stellen wir uns eine große sortierte Liste von Zahlen vor, vielleicht 10.000 Zahlen mit Werten zwischen 1 und 100.000. Wir gehen mal davon aus, dass diese Zahlen einigermaßen gleichmäßig verteilt sind, aber dennoch starken Zufallscharakter haben.

import java.util.Random;

public class Zufallszahlen
{
    final int max = 10000;
    int[] liste;
    
    public Zufallszahlen()
    {
        liste = new int[max];
        create();
        show();
    }
    
    public void create()
    {
        Random wuerfel = new Random();

        liste[0] = wuerfel.nextInt(10)+1;
        for (int i=1; i < max; i++)
           liste[i] = i*10 + wuerfel.nextInt(10)-5;
    }
    public void show()
    {
       for (int i=0; i < max; i++)
       {
          System.out.print(liste[i] + "\t");
          if ((i+1)%10==0)
             System.out.println();
       }
    }
}

Mit diesem kleinen Java-Quelltext kann man eine solche Liste erzeugen. Die Zahlen sind gleichmäßig verteilt und sehen zufällig aus. Hier ein Beispiel der Konsolenausgabe:

Ein Ausschnitt aus der Konsolenausgabe
Autor: Ulrich Helmich 2019, Lizenz: ---

Eine streng binäre Suche würde nun bei dem mittleren Element anfangen, das einen Wert um die 50.000 hätte. Wir wollen aber die Zahl 3.000 suchen. Wie könnten wir das sinnvoll machen?

Es ist klar, dass die 3.000 ziemlich weit vorne in dem Array steht. Aber wo genau soll die Suche beginnen?

Bei der Interpolationssuche wird der Einstiegs-Index in das Array mit einer einfachen Formel berechnet, die wir hier aber nicht näher besprechen wollen. Bei dieser Formel wird zunächst aus der ersten Zahl des Arrays und der letzten Zahl eine Spannweite berechnet.

Hier sehen wir das selbe Array wie im ersten Bild. Die Spannweite beträgt hier 99-2 = 97.

Dann wird die Anzahl der Arrayelemente berücksichtigt, hier 50.

Aus diesen beiden Werten und der Suchzahl selbst kann man dann den optimalen Einstiegs-Index in das Array berechnen.

Dieses Suchverfahren ist deutlich schneller als die binäre Suche, die Sprungsuche oder die Indexsuche. Bei einem Array aus 10.000 Zahlen im Bereich zwischen 1 und 50.000 benötigt die Interpolationssuche im Schnitt nur 3,2 Vergleiche - sagt zumindest die KI Mistral Vibe, der ich diese Aufgabe gestellt habe.

Diesen Vorteil hat die Interpolationssuche allerdings nur dann, wenn die Werte in dem Array tatsächlich einigermaßen gleichmäßig verteilt sind.

Wenn die Werte in dem Array nicht gleichmäßig verteilt sind, wäre die binäre Suche die beste Alternative.

In der Praxis (zum Beispiel bei großen Datenbanken) verwendet man oft sogenannte Hybridverfahren: Man startet mit einer Interpolationssuche und weicht auf binäre Suche aus, wenn die Schätzung schlecht greift. Oder man nutzt eine suchfreundlichere Struktur wie beispielsweise B-Bäume.