Binäre Suche

Harshit Jindal 12 Oktober 2023
  1. Binärer Suchalgorithmus
  2. Beispiel für binäre Suche
  3. Implementierung des binären Suchalgorithmus
  4. Binärer Suchalgorithmus Komplexität
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.

  • Setzen Sie lo auf 0 und hi auf n - 1.
  • Während lo < hi:
    • Setze mid = lo + (hi - lo)/2.
    • wenn A[mid] == X, mid zurückgibt.
    • wenn A[mid] < X dann lo= mid+1.
    • sonst wenn A[mid] > X dann hi= mid-1.
  • Element wird nicht gefunden, also wird -1 zurückgegeben.

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.

  • Setzen Sie lo als 0 und hi als 8.
  • Berechnen Sie mid als 4. Da A[mid] < X ist, setzen Sie lo = 4+1 =5.
  • Berechnen Sie mid als 6. Da A[mid]<X, setze lo =6+1 = 7.
  • Berechne mid als 7. Da A[mid] == 8, gebe 7 zurück.

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.

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Verwandter Artikel - Search Algorithm