Theoretische Informatik

1.2 Binäre Suche

Wenn wir im letzten Abschnitt eines gelernt haben, dann, dass lineare Suche schon bei kleineren Datenmengen zu viel Zeit benötigt. Falls Ihre Daten sortiert vorliegen, geht es schneller mit binärer Suche. Um das Prinzip der binären Suche zu verstehen, lade ich Sie dazu ein, ein kleines Spiel zu spielen.

Demo (binäre Suche)

Klicken Sie auf den Screenshot und spielen das Spiel.

Können Sie das gesuchte Wort mit höchstens sieben Klicks finden? Wahrscheinlich haben Sie rausgefunden, dass Sie als erstes irgendwo in der Mitte klicken sollten. Falls das dortige Wort "zu groß" ist, suchen Sie in der ersten Hälfte weiter; falls es zu klein ist, suchen Sie in der zweiten Hälfte weiter.

Versuchen wir nun, die Aufgabenstellung und das Prinzip der binären Suche genauer zu verstehen. Wir haben ein sortiertes Array $A$ der Größe $n$ gegeben, also $A[0] \leq A[1] \leq \dots \leq A[n-1]$. Auch haben wir einen Wert $x$ gegeben. Ziel ist es, die Position $i$ mit $A[i] = x$ zu finden oder zu dem Schluss zu kommen, dass $x$ im Array $A$ nicht vorkommt. Hierfür führen wir zwei Indizes $l$ und $u$, welche für lower bound und upper bound stehen. Für diese gilt immer \begin{equation} A[l] \leq x \lt A[u] \label{eqn-binary-search-invarant} \end{equation} gilt. Wir wählen anfangs $l=-1$ und $u = n$, wobei wir die Konvention im Hinterkopf haben, dass $A[i] = -\infty$ für $i \lt 0$ und $A[i] = \infty$ für $i \geq n$. Mit diesen "Randwerten" ist $A$ immer noch sortiert; allerdings müssen wir bei der Implementierung aufpassen, diese Array-Position nicht anzufassen. Die binäre Suche bildet nun das (abgerundete) arithmetisch Mittel zwischen $l$ und $u$, nämlich $$ m := \floor {\frac{l + u}{2} } $$ und schaut nach, ob $A[m]$ kleiner oder größer als $x$ oder im Besten Fall gleich $x$ ist. Wenn $x \lt A[m]$ gilt, setzen wir $u := m$; wenn $ A[m] \leq x $ gilt, dann setzen wir $l := m$; in jedem Fall gilt $(\ref{eqn-binary-search-invarant})$ auch für die neuen Schranken $l$ und $u$. Wir wiederholen diesen Schritt, bis $u = l + 1$ gilt. In diesem Falle gilt entweder $A[l] = x$ und wir haben $x$ gefunden, oder aber \begin{equation} A[l] \lt x \lt A[l+1] \ , \end{equation} woraus wir schlussfolgern können, dass $x$ gar nicht in $A$ vorkommt. In der Praxis würden wir natürlich sofort abbrechen, wenn $A[m] = x$ gilt; für eine theoretische Worst-Case-Analyse spielt dies allerdings keine Rolle.

Algorithmus (Binäre Suche)

Gegeben ein sortiertes Array $A[0..n-1]$ und einen Key $x$.

binarySearch(Array A, key x):                                
l := -1, u := m 
while u - l > 1: 
    m := (l+u)/2 
    if A[l] <= x then 
        l = m 
    else 
        u = m 
return m

Die Funktion binarySearch(A,x) gibt den größten Index $j \in \Z$ zurück, für den $A[j] \leq x$ gilt.

Extremfälle. Falls $x$ kleiner ist als alle Elemente in $A$, dann gibt binarySearch den Wert $-1$ zurück. Dies ist ja korrekt, da per Konvention $A[-1] = -\infty$ gilt und somit $A[-1] = -\infty \lt x$. Falls $x$ größer als alle Elemente in $A$ ist, gibt binarySearch den Wert $n-1$ zurück. Falls $A$ ein leeres Array ist, also $n=0$ gilt, dann ist $x$ jedoch sowohl kleiner als auch größer als alle Elemente von $A$. Die Funktion binarySearch müsste laut unseren vorherigen Angaben also sowohl $-1$ als auch $n-1$ zurückgeben. Dies stellt glücklicherweise keinen Widerspruch dar, da ja in diesem Falle $-1 = n-1$ gilt. (Der letzte Absatz klingt vielleicht pedantisch; es lohnt sich allerdings, solche Extremfälle durchzudenken, gerade wenn Sie vorhaben, Ihre Algorithmen auch zu implementieren.)

Laufzeitanalyse. Wenden wir uns der Frage zu, wie viele Schritte die while-Schleife in binarySearch im schlimmsten Falle durchläuft, in Abhängigkeit von $n$. Betrachten wir hierfür den Wert $u-l$ und wie er sich im Verlauf der Ausführung verändert. Nach einem Schleifendurchlauf wird der Wert $u-l$ entweder zu $$ \floor {\frac{u+l}{2}} - l $$ oder $$ u - \floor {\frac{u+l}{2}} \ , $$ je nachdem, ob wir im linken oder rechten Teilintervall weitersuchen.

Behauptung. $\floor {\frac{u+l}{2}} - l = \floor{ \frac {u-l}{2}} $ und $ u - \floor {\frac{u+l}{2}} = \ceil { \frac{u-l}{2}}$.

Beweis. Falls $u-l$ eine gerade Zahl ist, dann ist $u+l$ auch eine gerade Zahl, und wir können in allen Gleichungen die Aufrundungs- bzw. Abrundungsstriche weglassen. In diesem Falle sind die beiden Gleichungen also korrekt.

Falls nun $u-l$ eine ungerade Zahl ist, dann ist $u+l$ auch ungerade; des Weiteren gilt für ungerade Zahlen $k$, dass $\floor{\frac{k}{2}} = \frac{k-1}{2}$ und $\ceil{\frac{k}{2}} = \frac{k+1}{2}$. Die erste behauptete Gleichung wird also zu

$$ \floor {\frac{u+l}{2}} - l = \frac{u+l-1}{2} - l = \frac{u-l-1}{2} = \floor{ \frac{u-l}{2}} \ , $$ wie behauptet. Die zweite Gleichung wird zu $$u - \floor {\frac{u+l}{2}} = u - \frac{u+l-1}{2} = \frac{u-l+1}{2} = \ceil {\frac{u-l}{2}} \ ,$$ und beide Gleichungen gelten. $\square$

Setzen wir $k := u-l$. Wir sehen also, dass anfangs $k=n+1$ gilt und in jedem Durchlauf $k$ durch höchstens $\ceil{\frac{k}{2}}$ ersetzt wird. Wir enden, wenn $k=1$ erreicht ist.

Wieviele Schritte braucht es, bis aus $k=n+1$ schlussendlich $k=1$ geworden ist? Machen wir es uns einfach und betrachten den Fall, dass $k$ immer gerade ist (bis auf $k=1$), also zum Beispiel $8 \rightarrow 4 \rightarrow 2 \rightarrow 1$. Für $n=8$ brauchen wir also (im Worst Case) drei Schleifendurchläufe. Für $n=32$ erhalten wir $32 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$ und benötigen fünf Durchläufe. Unsere Beobachtung: wenn $n = 2^d$ gilt, die Länge unseres Arrays also eine Zweierpotenz ist, so wird binarySearch genau $d$ Schleifendurchläufe durchlaufen, also $\log_2(n)$ viele. Wenn nun $n$ etwas größer ist, also zum Beispiel $2^d + 1$, so durchläuft $k$ folgende Wertfolge: $$ 2^d + 1 \rightarrow 2^{d-1} + 1 \rightarrow \dots \rightarrow 9 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 1 $$ und wir benötigen insgesamt $d+1$ Durchläufe. Zusammenfassend: falls für den Startwert $k=n+1 \in \{2^{d-1}+1,\dots, 2^{d}\}$ gilt, so werden im Schlimmsten Fall $d$ Schleifendurchläufe benötigt. Kompakt lässt sich dies wie folgt formulieren:

Theorem Die Anzahl der Schleifendurchläufe von binarySearch auf einem Array aus $n$ Elementen ist im Worst Case $ \ceil{ \log_2 (n+1)}$.

Der genaue Ausdruck $ \ceil{ \log_2 (n+1)}$ ist schwierig zu merken. Allerdings wird es einfacher, wenn Sie sich folgende Beobachtung einprägen:

Beobachtung Die Binärdarstellung der Zahl $n$ besteht aus genau $ \ceil{ \log_2 (n+1)}$ Bits.

Also zum Beispiel $ (7)_2 = 111, (16)_2 = 1000$ und so weiter. Prägen Sie sich also zwei Dinge ein: (1) die binäre Suche auf einem Array mit $n$ Elementen braucht im schlimmsten Fall so viele Durchläufe, wie die Binärdarstellung der Zahl $n$ Bits hat; (2) dies ist ungefähr $\log_2(n)$.

Vergleichen wir nun die binäre Suche mit der linearen. Falls das Array $A$ unsortiert ist und wir $x$ suchen, dann müssen wir im Worstcase alle $n$ Elemente von $A$ durchgehen. Wenn $A$ sortiert ist und wir binäre Suche verwenden, dann reduziert sich dies auf höchstens $ \ceil{ \log_2 (n+1)}$ Zugriffe. Vergleichen wir nun lineare Suche und binäre Suche in der Praxis.

Demo

Analog zu Set.java habe ich OrderedSet.java geschrieben. Dies liest die (bereits sortierte) Datei english-words-58110.txt ein und beantwortet dann Anfragen. Vergleichen wir nun die Laufzeiten:

time java Set english-words-58110.txt < german-50000.txt > /dev/null                            

real	2m47.048s
user	2m20.644s
sys	0m1.403s

time java SortedSet english-words-58110.txt < german-50000.txt > /dev/null

real	0m0.559s
user	0m0.968s
sys	0m0.120s

Durch binäre Suche haben wir die Laufzeit um einen Faktor von 300 reduziert!

Binäre Suche taucht auch oft auf, ohne dass explizit ein Array vorliegt.

Übungsaufgabe

Schreiben Sie in Java eine Funktion public static int sqrt (int n), die die Funktion $$ n \mapsto \floor {\sqrt{n}} $$ berechnet. Verwenden Sie nicht Math.sqrt oder andere mathematische Bibliotheksfunktionen.

Übungsaufgabe

Ich habe Ihnen einen speziellen Algorithmus vorgestellt, der das gegenwärtige Suchareal in jedem Schritt halbiert. Ist dies optimal? Versuchen Sie zu beweisen, dass man im Schlimmsten Fall auch $ \ceil { \log_2 (n+1)}$ Schritte benötigt.

Formulieren Sie in Gedanken die binäre Suche als Spiel . Bob kennt das Array $A$. In jedem Schritt fragt Alice einen index $i$ an und Bob antwortet mit $A[i]$. Alice will möglichst schnell den Wert $x$ finden, und Bob will dies verzögern.
Tun Sie so, als wäre Bob ein adaptiver Gegner. Das heißt, er kann sich das Array $A$ Schritt für Schritt während des Spiels ausdenken. Er muss aber immer konsistent antworten, d.h. wenn Alice sowohl die Indizes $i \lt j$ angefragt hat, müssen Bobs Antworten die Bedingung $A[i] \lt A[j]$ erfüllen.
Zeigen Sie, dass Sie den adaptiven Bob durch einen nicht-adaptiven Bob ersetzen können (also durch ein Array $A$, dass von vornherein feststeht), so dass Alice dennoch nicht schneller zum Ziel kommt (hier ist es wichtig, dass Alice deterministisch ist, also keinen Zufall verwenden darf).

Da binäre Suche ein ganz allgemeines Prinzip ist, ist es sinnvoll, es etwas abstrakter zu formulieren.

Wir haben ein sortiertes Array aus $n$ ganzen Zahlen. Finde die erste nicht-negative Zahl.
Wir haben ein Array aus $n$ ganzen Zahlen, in welchem die negativen Zahlen links von allen positiven Zahlen stehen. Finde die erste positive Zahl.
Wir haben ein Array $A$ aus $n$ ganzen Zahlen, wobei $A[0] \lt 0$ und $A[n-1] \geq 0$ gelten. Finde einen Index $i$ mit $A[i] \lt 0 \leq A[i+1]$.