Interpolationssuche (manchmal gekennzeichnet als Extrapolationssuche) ist ein Algorithmus, für nach einem gegebenen Schlüsselwert in einer mit einem Inhaltsverzeichnis versehenen Reihe zu suchen, die durch die Werte des Schlüssels bestellt worden ist. Es passt an, wie Menschen ein Telefonbuch für einen besonderen Namen, den Schlüsselwert durchsuchen, durch den die Einträge des Buches bestellt werden. In jedem Suchschritt rechnet es, wo im restlichen Suchraum der gesuchte Artikel, gestützt auf den Schlüsselwerten an den Grenzen des Suchraums und dem Wert des gesuchten Schlüssels gewöhnlich über eine geradlinige Interpolation sein könnte. Der an dieser geschätzten Position wirklich gefundene Schlüsselwert ist dann im Vergleich zum Schlüsselwert, der wird sucht. Wenn es nicht gleich ist, dann abhängig vom Vergleich wird der restliche Suchraum auf den Teil vorher oder nach der geschätzten Position reduziert. Diese Methode wird nur arbeiten, wenn Berechnungen auf der Größe von Unterschieden zwischen Schlüsselwerten vernünftig sind.

Vergleichsweise wählt die binäre Suche immer die Mitte des restlichen Suchraums, eine Hälfte oder den anderen wieder abhängig vom Vergleich zwischen dem Schlüsselwert verwerfend, der an der geschätzten Position und dem gesuchten Schlüsselwert gefunden ist. Der restliche Suchraum wird auf den Teil vorher oder nach der geschätzten Position reduziert. Die geradlinige Suche verwendet Gleichheit nur, weil es Elemente eins nach dem anderen vom Anfang vergleicht, jedes Sortieren ignorierend.

Durchschnittlich macht die Interpolationssuche über den Klotz (Klotz (n)) Vergleiche (wenn die Elemente gleichförmig verteilt werden), wo n die Zahl der Elemente ist, um gesucht zu werden. Im Grenzfall (zum Beispiel, wo die numerischen Werte der Schlüssel exponential zunehmen) kann es bis zu O (n) Vergleiche machen.

In der auf die Interpolation folgenden Suche wird Interpolation verwendet, um einen Artikel in der Nähe von demjenigen zu finden, der wird sucht, dann wird geradlinige Suche verwendet, um den genauen Artikel zu finden.

Leistung

Mit der großen-O Notation ist die Leistung des Interpolationsalgorithmus auf einer Datei der Größe N O (N); jedoch unter der Annahme einer Rechteckverteilung der Daten auf der geradlinigen für die Interpolation verwendeten Skala, wie man zeigen kann, ist die Leistung O (Klotz loggen N).. Jedoch ist Dynamische Interpolationssuche in o möglich (Klotz loggen n) die Zeit mit einer neuartigen Datenstruktur.

Die praktische Leistung der Interpolationssuche hängt ab, ob die verminderte Anzahl von Untersuchungen durch die mehr komplizierten für jede Untersuchung erforderlichen Berechnungen überwogen wird. Es kann nützlich sein, für eine Aufzeichnung in einer großen sortierten Datei auf der Platte ausfindig zu machen, wo jede Untersuchung mit einer Platte verbunden ist, suchen, und ist viel langsamer als die Interpolationsarithmetik.

Index-Strukturen wie B-Bäume vermindern auch die Anzahl von Plattenzugängen, und werden öfter verwendet, um Daten auf der Platte teilweise mit einem Inhaltsverzeichnis zu versehen, weil sie viele Typen von Daten mit einem Inhaltsverzeichnis versehen können und online aktualisiert werden können. Und doch, Interpolationssuche kann nützlich sein, wenn einer gezwungen wird, bestimmten sortierten, aber mit einem Inhaltsverzeichnis unersehenen datasets auf der Platte zu suchen.

Anpassung an verschiedenen datasets

Wenn Sorte-Schlüssel für einen dataset gleichförmig verteilte Zahlen sind, ist geradlinige Interpolation aufrichtig, um durchzuführen, und wird einen Index sehr in der Nähe vom gesuchten Wert finden.

Andererseits, für ein Telefonbuch sortiert namentlich, gilt die aufrichtige Annäherung an die Interpolationssuche nicht. Dieselben Grundsätze auf höchster Ebene können noch, obwohl gelten: Man kann eine Position eines Namens im Telefonbuch mit den Verhältnisfrequenzen von Briefen in Namen und Gebrauch dass als eine Untersuchungsposition schätzen.

Einige Interpolationssuchdurchführungen, können wie erwartet, nicht arbeiten, wenn ein Lauf von gleichen Schlüsselwerten besteht. Die einfachste Durchführung der Interpolationssuche wird das erste (oder letzt) Element solch eines Laufs nicht notwendigerweise auswählen. Die Interpolationsberechnung muss auch geschrieben werden, um Abteilung durch die Null zu vermeiden.

Buchbasierte Suche

Die Konvertierung von Namen in einem Telefonbuch zu einer Art Zahl wird klar Zahlen nicht zur Verfügung stellen, die eine Rechteckverteilung (außer über die riesige Anstrengung wie das Sortieren der Namen und Benennen von ihnen Name #1, Name #2, usw.) und weiter haben, es ist wohl bekannt, dass einige Namen viel üblicher sind als andere (Schmied, Jones,) Ähnlich mit Wörterbüchern, wo es noch viele Wörter gibt, die mit einigen Briefen anfangen als andere. Einige Herausgeber gehen zur Anstrengung, Randanmerkungen vorzubereiten oder sogar in die Seite der Seiten zu schneiden, um Anschreiber für jeden Brief zu zeigen, so dass mit einem flüchtigen Blick eine segmentierte Interpolation durchgeführt werden kann.

Beispieldurchführung

Das folgende Codebeispiel für die javanische Programmiersprache ist eine einfache Durchführung. In jeder Bühne schätzt es eine Untersuchungsposition dann als mit der binären Suche, Bewegungen entweder das obere oder niedrigere, das gebunden ist in, einen kleineren Zwischenraum zu definieren, der den gesuchten Wert enthält. Verschieden von der binären Suche, die ein Halbieren der Größe des Zwischenraums mit jeder Bühne versichert, kann eine verführte Interpolation die Mitte Index um nur einen reduzieren/vergrößern, so auf eine Grenzfall-Leistungsfähigkeit von O (n) hinauslaufend.

öffentliche interne Nummer interpolationSearch (interne Nummer [] sortedArray, interne Nummer toFind) {\

//Rückindex von toFind in sortedArray, oder-1 wenn nicht gefundener

interne Nummer niedrig = 0;

interne Nummer hoch = sortedArray.length - 1;

int Mitte;

während (sortedArray [niedrig]

Mitte = niedrig +

((toFind - sortedArray [niedrig]) * (hoch - niedrig)) /

(sortedArray [hoch] - sortedArray [niedrig]);//ist außer Reichweite hier möglich

wenn (sortedArray [Mitte]

//Die Wiederholung des Vergleich-Codes wird durch Syntax-Beschränkungen gezwungen.

hoch = Mitte - 1;

sonst

geben Sie Mitte zurück;

}\

wenn (sortedArray [niedrig] == toFind)

kehren Sie niedrig zurück;

sonst

kehren Sie-1 zurück;//Nicht gefundener

}\

</Quelle>

Bemerken Sie, dass, die Liste am Index untersucht, Mitte, aus Gründen der Schleife-Kontrollregierung, dieser Code entweder hoch oder niedrig untergeht, nicht Mitte, aber ein angrenzender Index zu sein, welche Position dann während der folgenden Wiederholung untersucht wird. Da ein Wert eines angrenzenden Zugangs viel nicht verschieden sein wird, wird die Interpolationsberechnung durch diese Schritt-Anpassung auf Kosten einer zusätzlichen Verweisung auf das entfernte Gedächtnis wie Scheibe nicht sehr verbessert.

Jede Wiederholung des obengenannten Codes verlangt zwischen fünf und sechs Vergleichen (das zusätzliche ist wegen der Wiederholungen musste die drei Staaten dessen unterscheiden

Siehe auch

• Geradlinige Suche
• Binäre Suche
• Dreifältige Suche
• Hash-Tabelle

Links

• Interpolationssuche
• Nationales Institut für Standards und Technologie
• Interpolationssuche - ein Klotz Suche von LogN