Datenstruktur - Interpolationssuche

Die Interpolationssuche ist eine verbesserte Variante der binären Suche. Dieser Suchalgorithmus arbeitet an der Prüfposition des erforderlichen Werts. Damit dieser Algorithmus ordnungsgemäß funktioniert, sollte die Datenerfassung sortiert und gleichmäßig verteilt sein.

Die binäre Suche hat einen großen Vorteil der Zeitkomplexität gegenüber der linearen Suche. Die lineare Suche hat die Worst-Case-Komplexität von Ο (n), während die binäre Suche Ο (log n) hat.

Es gibt Fälle, in denen der Ort der Zieldaten im Voraus bekannt sein kann. Zum Beispiel im Fall eines Telefonverzeichnisses, wenn wir die Telefonnummer von Morphius suchen möchten. Hier scheint die lineare Suche und sogar die binäre Suche langsam zu sein, da wir direkt in den Speicherbereich springen können, in dem die Namen ab 'M' gespeichert sind.

Positionierung in der binären Suche

Wenn bei der binären Suche die gewünschten Daten nicht gefunden werden, wird der Rest der Liste in zwei Teile geteilt, niedriger und höher. Die Suche wird in einem von beiden durchgeführt.

Selbst wenn die Daten sortiert sind, nutzt die binäre Suche nicht den Vorteil, die Position der gewünschten Daten zu prüfen.

Positionsabtastung in der Interpolationssuche

Die Interpolationssuche findet ein bestimmtes Element durch Berechnen der Sondenposition. Zu Beginn ist die Sondenposition die Position des mittelsten Elements der Sammlung.

Wenn eine Übereinstimmung auftritt, wird der Index des Elements zurückgegeben. Um die Liste in zwei Teile zu teilen, verwenden wir die folgende Methode:

mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

where −
   A    = list
   Lo   = Lowest index of the list
   Hi   = Highest index of the list
   A[n] = Value stored at index n in the list

Wenn das mittlere Element größer als das Element ist, wird die Sondenposition erneut im Unterarray rechts vom mittleren Element berechnet. Andernfalls wird das Element im Subarray links vom mittleren Element gesucht. Dieser Prozess wird auch auf dem Subarray fortgesetzt, bis die Größe des Subarrays auf Null reduziert ist.

Die Laufzeitkomplexität des Interpolationssuchalgorithmus ist Ο(log (log n)) verglichen mit Ο(log n) von BST in günstigen Situationen.

Algorithmus

Da es sich um eine Improvisation des vorhandenen BST-Algorithmus handelt, erwähnen wir die Schritte zum Durchsuchen des 'Ziel'-Datenwertindex mithilfe der Positionsprüfung -

Step 1 − Start searching data from middle of the list.
Step 2 − If it is a match, return the index of the item, and exit.
Step 3 − If it is not a match, probe position.
Step 4 − Divide the list using probing formula and find the new midle.
Step 5 − If data is greater than middle, search in higher sub-list.
Step 6 − If data is smaller than middle, search in lower sub-list.
Step 7 − Repeat until match.

Pseudocode

A → Array list
N → Size of A
X → Target Value

Procedure Interpolation_Search()

   Set Lo  →  0
   Set Mid → -1
   Set Hi  →  N-1

   While X does not match
   
      if Lo equals to Hi OR A[Lo] equals to A[Hi]
         EXIT: Failure, Target not found
      end if
      
      Set Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo]) 

      if A[Mid] = X
         EXIT: Success, Target found at Mid
      else 
         if A[Mid] < X
            Set Lo to Mid+1
         else if A[Mid] > X
            Set Hi to Mid-1
         end if
      end if
   End While

End Procedure

Klicken Sie hier , um mehr über die Implementierung der Interpolationssuche in der Programmiersprache C zu erfahren .