Binäre Suche

Einfache Sprache

Binäre Suche ist ein Suchalgorithmus um den Index eines Elements in einem sortieren Feld zu finden. Dazu wird immer das Element genau in der Mitte angeschaut und abhängig davon die Suche in der kleineren bzw. größeren Hälfte vortsetzten.

Idee Binäre Suche

Gegeben ist ein sortiertes Feld $A$ mit $n$ Zahlen (d.h. $A[0] \leq A[1] \leq \ldots \leq A[n − 1]$) und eine Zahl $x$. Gesucht ist eine Index $i$ mit $A[i]=x$ (oder die Mittelung, dass $x$ nicht in $A$ enthalten ist). Dafür verwenden wir die Idee, dass wir $x$ jeweils mit dem Element in der Mitte vergleichen. $i$ und $j$ sind die Indizes für für die untere bzw. obere Grenze des aktuellen Suchbereichs (am Anfang ist $\textrm{mid}=\lfloor(n-1)/2\rfloor$), $i = 0$ und $j = n-1$. Es gibt drei Mögliche Fälle:

1. $A[\textrm{mid}] = x$. Element ist gefunden.
2. $A[\textrm{mid}] < x$. $x$ wird in der oberen Hälfte des Feldes liegen (falls $x$ in $A$ liegt).
3. $A[\textrm{mid}] > x$. $x$ wird in der untern Hälfte des Feldes liegen (falls $x$ in $A$ liegt).

Algorithmus

 1def binary_search(A, x):
 2    n = len(A)
 3    i = 0
 4    j = n-1
 5    found = False
 6    while i <= j and not found:
 7        mid = (i + j) // 2 # Floor devision.
 8        if x < A[mid]:
 9            j = mid - 1
10        elif x > A[mid]:
11            i = mid + 1
12        else:
13            found = True
14    return mid if found else -1

Laufzeit

Binäre Suche hat eine Laufzeit von $\mathcal O(\log_2 n)$.