Interpolationssuche

1. Interpolations-Suchalgorithmus
2. Beispiel für die Interpolationssuche
3. Implementierung des Interpolationssuchalgorithmus
4. Interpolationssuchalgorithmus Komplexität

Die Interpolationssuche ist ein schneller und effizienter Suchalgorithmus. Er verbessert den binären Suchalgorithmus für Szenarien, in denen Arrayelemente gleichmäßig über das sortierte Array verteilt sind. Er arbeitet an der Sondierungsposition des gesuchten Wertes. Im Gegensatz zur binären Suche geht er nicht immer zur Mitte des Arrays, sondern kann zu jeder beliebigen Position gehen, abhängig vom Wert des zu suchenden Schlüssels. Wir vergleichen den Wert an der geschätzten Position und reduzieren den Suchraum auf den Teil nach oder vor ihm. Wenn wir z. B. ein Wort im Dictionary suchen, blättern wir die Seiten entsprechend der Position der Buchstaben im Dictionary und nicht, indem wir den Suchraum jedes Mal in zwei Hälften aufteilen.

Interpolations-Suchalgorithmus

Nehmen wir an, wir haben ein unsortiertes Array A[], das n Elemente enthält, und wir wollen ein bestimmtes Element X finden.

Beispiel für die Interpolationssuche

Angenommen, wir haben das Array: (1, 3, 7, 8, 11, 15, 17, 18, 21), und wir wollen X - 18 finden.

Implementierung des Interpolationssuchalgorithmus

#include <bits/stdc++.h>
using namespace std;

int interpolation_search(int arr[], int n, int X) {
  int lo = 0;
  int hi = n - 1;
  int mid;

  while ((arr[hi] != arr[lo]) && (X >= arr[lo]) && (X <= arr[hi])) {
    mid = lo + ((X - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]));

    if (arr[mid] < X)
      lo = mid + 1;
    else if (X < arr[mid])
      hi = mid - 1;
    else
      return mid;
  }

  if (X == arr[lo])
    return lo;
  else
    return -1;
}

int main(void) {
  int n = 9;
  int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  int x = 4;
  int result = interpolation_search(arr, n, x);
  if (result == -1) {
    cout << "Element not found !!";
  } else
    cout << "Element found at index " << result;
  return 0;
}

Interpolationssuchalgorithmus Komplexität

Zeitkomplexität

• Durchschnittlicher Fall

Die Zeitkomplexität des Algorithmus im durchschnittlichen Fall liegt in der Größenordnung von O(log(logn)). Dies ist der Fall, wenn alle Elemente innerhalb des Arrays gleichmäßig verteilt sind.

• Bester Fall

Der Best-Case tritt auf, wenn das gesuchte Element das erste Element ist, das durch die Interpolationssuche untersucht wird. Die Best-Case-Zeitkomplexität des Algorithmus ist O(1).

• Schlechtester Fall

Der Worst-Case tritt auf, wenn die numerischen Werte der Ziele exponentiell ansteigen. Die Worst-Case-Zeitkomplexität des Algorithmus ist O(n).

Raumkomplexität

Die Raumkomplexität dieses Algorithmus ist O(1), da er außer temporären Variablen keine weitere Datenstruktur benötigt.