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 auf der vorherigen Seite erklärt wurde.

Umsetzung der Interpolationssuche

Stellen wir uns eine große sortierte Liste von Zahlen vor, beispielsweise 10.000 Zahlen mit Werten zwischen 1 und 100.000. Wir gehen davon aus, dass diese Zahlen annähernd gleichmäßig über den Wertebereich verteilt sind, aber dennoch einen gewissen Zufallscharakter besitzen.

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 - 5 + wuerfel.nextInt(10);
    }

    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-Programm können wir eine solche Liste erzeugen. Die Zahlen sind annähernd gleichmäßig verteilt, besitzen aber einen zufälligen Anteil. Da sich die Werte aufeinanderfolgender Arrayelemente nicht überschneiden können, ist das Array stets aufsteigend sortiert. Hier ein Ausschnitt aus der Konsolenausgabe:

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

Eine binäre Suche würde zunächst das mittlere Arrayelement untersuchen, das ungefähr den Wert 50.000 besitzt. Wir wollen aber die Zahl 3.000 suchen. Da die Zahlen annähernd gleichmäßig verteilt sind, können wir vermuten, dass sich die gesuchte Zahl ziemlich weit vorne im Array befindet.

Aber wo genau sollten wir mit der Suche beginnen? Hier kommt die Grundidee der Interpolationssuche ins Spiel: Wir schätzen die Position der Suchzahl anhand ihrer relativen Lage innerhalb des gesamten Wertebereichs.

Berechnung der Einstiegsposition

Bei der Interpolationssuche wird der vermutete Index der Suchzahl mit folgender Formel berechnet:

$\text{Position} = \frac{S - \text{array}[0]}{W} \cdot (L-1)$

Dabei bedeuten:

• S = die Suchzahl
• W = die Spannweite der Zahlen, also array[L-1] - array[0]
• L = die Länge des Arrays
• array[0] = der kleinste Wert im Array

Die Formel setzt voraus, dass das Array aufsteigend sortiert ist, die Suchzahl innerhalb des Wertebereichs liegt und die Spannweite größer als 0 ist. Je gleichmäßiger die Zahlen verteilt sind, desto genauer ist in der Regel die berechnete Position.

Erstes Suchbeispiel: Die Zahl 47

Betrachten wir dazu ein Array aus 50 sortierten int-Zahlen im Bereich von 2 bis 99:

Die Spannweite W beträgt 99 - 2 = 97. Die Arraylänge L ist 50. Als Suchzahl wählen wir zunächst S = 47.

Mit der obigen Formel berechnen wir folgende Einstiegsposition:

$\text{Position} = \frac{47-2}{97} \cdot 49 = \frac{45}{97} \cdot 49 \approx 22{,}7$

Da ein Arrayindex ganzzahlig sein muss, schneiden wir den Nachkommateil des Ergebnisses ab. Wir beginnen daher bei Index 22. Dort steht die Zahl 46, die etwas kleiner als unsere Suchzahl ist.

Bei unserer etwas vereinfachten Variante der Interpolationssuche könnten wir nun sequentiell nach rechts weitersuchen. An Index 23 steht die Zahl 48, die bereits größer als unsere Suchzahl ist. Nach zwei Vergleichen mit Arrayelementen können wir die Suche also abbrechen: Die Zahl 47 kommt in diesem Array nicht vor.

Bei der eigentlichen Interpolationssuche würde man dagegen nach dem ersten erfolglosen Vergleich den Suchbereich verkleinern und innerhalb dieses Bereichs erneut eine Position berechnen. Auf diese Weise nähert man sich der gesuchten Zahl schrittweise an, ohne sämtliche dazwischenliegenden Elemente untersuchen zu müssen.

Zweites Suchbeispiel: Die Zahl 58

Versuchen wir es mit einer anderen Suchzahl. Diesmal suchen wir die Zahl 58, die tatsächlich im Array vorkommt.

$\text{Position} = \frac{58-2}{97} \cdot 49 = \frac{56}{97} \cdot 49 \approx 28{,}3$

Nach Abschneiden des Nachkommateils erhalten wir den Index 28. Dort steht tatsächlich die Zahl 58. Wir haben die Suchzahl also bereits beim ersten Vergleich gefunden!

Eine binäre Suche hätte dagegen fünf Suchschritte benötigt, um das Element an Index 28 zu finden. Sie hätte nacheinander die Indizes 24, 37, 30, 27 und schließlich 28 untersucht.

Fazit:

Unsere beiden Beispiele zeigen, wie leistungsfähig die Interpolationssuche bei annähernd gleichmäßig verteilten Zahlen sein kann. Während die binäre Suche den Suchbereich bei jedem Schritt ungefähr halbiert, versucht die Interpolationssuche, die Position der Suchzahl anhand ihres Wertes möglichst genau vorherzusagen.