Exponentiale Suche

1. Exponentialer Suchalgorithmus
2. Exponentialsuche Beispiel
3. Implementierung des Exponentialsuchalgorithmus
4. Exponentieller Suchalgorithmus Komplexität

Die Exponentialsuche, auch bekannt als Verdopplungssuche oder Fingersuche, ist ein Algorithmus, der für die Suche von Elementen in sehr großen Arrays entwickelt wurde. Es ist ein zweistufiger Prozess. Zunächst versucht der Algorithmus, den Bereich (L, R) zu finden, in dem sich das Zielelement befindet, und verwendet dann die binäre Suche innerhalb dieses Bereichs, um die genaue Position des Ziels zu finden.

Er heißt Exponentialsuche, weil er den Bereich findet, in dem das Element vorhanden ist, indem er nach dem ersten Exponenten k sucht, für den das Element mit dem Index pow(2,k) größer als das Zielelement ist. Obwohl sein Name Exponentialsuche lautet, ist die Zeitkomplexität dieses Algorithmus logarithmisch. Er ist sehr nützlich, wenn Arrays unendlich groß sind und konvergiert viel schneller zu einer Lösung als die binäre Suche.

Exponentialer Suchalgorithmus

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

Exponentialsuche Beispiel

Angenommen, wir haben das Array: (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11), und wir wollen X - 10 finden.

Implementierung des Exponentialsuchalgorithmus

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

int binarySearch(int arr[], int lo, int hi, int x) {
  while (lo <= hi) {
    int m = lo + (hi - lo) / 2;
    if (arr[m] == x) return m;
    if (arr[m] < x)
      lo = m + 1;
    else
      hi = m - 1;
  }
  return -1;
}

int exponentialSearch(int arr[], int n, int x) {
  if (arr[0] == x) return 0;
  int i = 1;
  while (i < n && arr[i] <= x) i = i * 2;

  return binarySearch(arr, i / 2, min(i, n - 1), x);
}

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

Exponentieller Suchalgorithmus Komplexität

Zeitkomplexität

• Durchschnittlicher Fall

Die durchschnittliche Zeitkomplexität ist O(logi), wobei i der Index des Zielelements X innerhalb des Arrays ist. Er übertrifft sogar die binäre Suche, wenn das Element nahe am Anfang des Arrays liegt.

• Bester Fall

Der beste Fall tritt ein, wenn das Element, das wir vergleichen, das gesuchte Element ist und in der ersten Iteration zurückgegeben wird. Die Zeitkomplexität im besten Fall ist O(1).

• Schlechtester Fall

Die Zeitkomplexität im schlimmsten Fall entspricht der Zeitkomplexität im durchschnittlichen Fall. Die Worst-Case-Zeitkomplexität ist O(logi).

Raumkomplexität

Die Platzkomplexität dieses Algorithmus ist O(1), da er außer temporären Variablen keinen weiteren Platz benötigt.