Interpolationssuche in Java

1. Einleitung

In diesem Tutorial werden wir die Interpolationssuchalgorithmen durchgehen und ihre Vor- und Nachteile diskutieren. Darüber hinaus werden wir es in Java implementieren und über die zeitliche Komplexität des Algorithmus sprechen.

2. Motivation

Die Interpolationssuche ist eine Verbesserung gegenüber der binären Suche, die auf gleichmäßig verteilte Daten zugeschnitten ist.

Die binäre Suche halbiert den Suchraum bei jedem Schritt unabhängig von der Datenverteilung, daher ist die zeitliche Komplexität immer O (log (n)) .

Andererseits variiert die Komplexität der Interpolationssuchzeit in Abhängigkeit von der Datenverteilung . Es ist schneller als die binäre Suche nach gleichmäßig verteilten Daten mit der zeitlichen Komplexität von O (log (log (n))) . Im schlimmsten Fall kann es jedoch so schlecht wie O (n) sein .

3. Interpolationssuche

Ähnlich wie bei der binären Suche kann die Interpolationssuche nur in einem sortierten Array ausgeführt werden. Bei jeder Iteration wird eine Sonde an einer berechneten Position platziert. Befindet sich die Sonde genau auf dem gesuchten Objekt, wird die Position zurückgegeben. Andernfalls ist der Suchraum entweder auf die rechte oder die linke Seite der Sonde beschränkt.

Die Sondenpositionsberechnung ist der einzige Unterschied zwischen der binären Suche und der Interpolationssuche.

Bei der binären Suche ist die Sondenposition immer das mittlere Element des verbleibenden Suchraums.

Im Gegensatz dazu berechnet die Interpolationssuche die Sondenposition basierend auf dieser Formel:

Werfen wir einen Blick auf die einzelnen Begriffe:

  • Sonde : Die neue Sondenposition wird diesem Parameter zugewiesen.
  • lowEnd : Der Index des Elements ganz links im aktuellen Suchbereich.
  • highEnd : Der Index des Elements ganz rechts im aktuellen Suchbereich.
  • data [] : Das Array, das den ursprünglichen Suchraum enthält.
  • Artikel : Der Artikel, den wir suchen.

Um die Funktionsweise der Interpolationssuche besser zu verstehen, zeigen wir sie anhand eines Beispiels.

Angenommen, wir möchten die Position 84 im folgenden Array finden:

Die Länge des Arrays beträgt 8, also anfänglich highEnd = 7 und lowEnd = 0 (da der Index des Arrays bei 0 beginnt und nicht bei 1).

Im ersten Schritt ergibt die Sondenpositionsformel Sonde = 5:

Da 84 (der Artikel die wir suchen) größer als 73 (die aktuelle Sonde Position Artikel), wird der nächste Schritt für die Zuordnung der linke Seite des Feldes verläßt lowend = Sonde + 1. Nun ist der Suchraum besteht aus nur 84 und 101. Die Sondenpositionsformel setzt Sonde = 6, was genau dem Index der 84 entspricht:

Da der gesuchte Artikel gefunden wurde, wird Position 6 zurückgegeben.

4. Implementierung in Java

Nachdem wir verstanden haben, wie der Algorithmus funktioniert, implementieren wir ihn in Java.

Zuerst initialisieren wir lowEnd und highEnd :

int highEnd = (data.length - 1); int lowEnd = 0;

Als nächstes richten wir eine Schleife ein und berechnen in jeder Iteration die neue Sonde basierend auf der oben genannten Formel. Die Schleifenbedingung stellt sicher, dass wir uns nicht außerhalb des Suchraums befinden, indem wir das Element mit den Daten [lowEnd] und data [highEnd] vergleichen :

while (item >= data[lowEnd] && item <= data[highEnd] && lowEnd <= highEnd) { int probe = lowEnd + (highEnd - lowEnd) * (item - data[lowEnd]) / (data[highEnd] - data[lowEnd]); }

Wir prüfen auch, ob wir den Artikel nach jeder neuen Sondenzuweisung gefunden haben .

Schließlich passen wir lowEnd oder highEnd an, um den Suchraum bei jeder Iteration zu verringern:

public int interpolationSearch(int[] data, int item) { int highEnd = (data.length - 1); int lowEnd = 0; while (item >= data[lowEnd] && item <= data[highEnd] && lowEnd <= highEnd) { int probe = lowEnd + (highEnd - lowEnd) * (item - data[lowEnd]) / (data[highEnd] - data[lowEnd]); if (highEnd == lowEnd) { if (data[lowEnd] == item) { return lowEnd; } else { return -1; } } if (data[probe] == item) { return probe; } if (data[probe] < item) { lowEnd = probe + 1; } else { highEnd = probe - 1; } } return -1; }

5. Schlussfolgerung

In diesem Artikel haben wir die Interpolationssuche anhand eines Beispiels untersucht. Wir haben es auch in Java implementiert.

Die in diesem Tutorial gezeigten Beispiele sind auf Github verfügbar.