Binäre Suche

Die binäre Suche ist der beliebteste und effizienteste Suchalgorithmus. In der Tat ist es der schnellste Suchalgorithmus. Genau wie die Sprungsortierung benötigt auch er das zu sortierende Array. Er basiert auf dem Divide-and-Conquer-Ansatz, bei dem das Array in zwei Hälften geteilt wird und dann das gesuchte Element mit dem mittleren Element verglichen wird. Wenn das mittlere Element übereinstimmt, geben wir den Index des mittleren Elements zurück; andernfalls bewegen wir uns je nach Wert des Elements zur linken oder rechten Hälfte.

Binärer Suchalgorithmus

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

Beispiel für binäre Suche

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

Implementierung des binären Suchalgorithmus

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

Binärer Suchalgorithmus Komplexität

Zeitkomplexität

• Durchschnittlicher Fall

Wenn wir die binäre Suche durchführen, suchen wir in einer Hälfte und verwerfen die andere Hälfte, wodurch die Größe des Arrays jedes Mal um die Hälfte reduziert wird.

Der Ausdruck für die Zeitkomplexität ist durch die Rekursion gegeben.

T(n) = T(n/2) + k , k is a constant.

Das Ergebnis dieser Rekursion ergibt logn, und die Zeitkomplexität liegt in der Größenordnung von O(logn). Sie ist schneller als sowohl die lineare Suche als auch die Sprungsuche.

• Bester Fall

Der Best-Case tritt auf, wenn das mittlere Element 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 ist die gleiche wie die Zeitkomplexität im mittleren Fall. Die Zeitkomplexität im schlimmsten Fall ist O(logn).

Raumkomplexität

Die Platzkomplexität dieses Algorithmus ist O(1) im Falle einer iterativen Implementierung, da er keine andere Datenstruktur als temporäre Variablen benötigt.

Im Falle einer rekursiven Implementierung ist die Platzkomplexität O(logn) aufgrund des Platzbedarfs für den Stack der rekursiven Aufrufe.