TI

Abstraktion

Wir abstrahieren nun von unserem Beispiel mit den englischen Vokabeln und versuchen, die Aufgabenstellung und das Prinzip der binären Suche genauer zu verstehen. Wir haben ein Array $A$ der Größe $n$ gegeben. Es ist sortiert, es gilt also $A[0] \leq A[1] \leq \dots \leq A[n-1]$. Lassen Sie sich von dem mathematischen Symbol $\leq$ nicht täuschen. Es muss sich bei den Elementen $A[i]$ nicht um Zahlen handeln. Ganz generell kommen die Elemente aus einem Universum $\mathcal{U}$, auf dem eine lineare Ordnung definiert ist. Ohne jetzt definieren zu wollen, was das genau bedeutet, sei nur dies gesagt: die Elemente lassen sich vergleichen. In englishVocabulary.txt beispielsweise haben wir Strings gegeben, die wir alphabetisch (Mathematiker würden sagen: lexikographisch) vergleichen können.

Des Weiteren haben wir einen Suchwert $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{align} A[l] \leq x \lt A[u] \label{eqn-binary-search-invariant} \end{align} 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$.

Konvention: $A[i] = -\infty$ für alle $i \lt 0$ und $A[i] = \infty$ für alle $i \geq n$. Insbesondere also $A[-1] = -\infty$ und $A[n] = \infty$.

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) arithmetische 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-invariant})$ 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, Pseudocode)

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

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

Um zu zeigen, dass der obige Code korrekt ist, müssen wir erst genau formulieren, was wir denn von der binären Suche erwarten:

Theorem Die Funktion binarySearch(A,x) gibt den eindeutigen Index $j \in \{-1,0,\dots,n-1\}$ zurück, für den $A[j] \leq x \lt A[j+1]$ gilt.

Hinweis: Ob die Aussage im Theorem das beschreibt, was Sie wollen, ist eventuell Geschmackssache. Eine Variante wäre zum Beispiel, zu verlangen, dass der Algorithmus $n$ zurückgibt, falls $x$ größer ist als alle Elemente in dem sortieren Array. Dafür müssten wir den Pseudocode etwas modifizieren.

Extremfälle: Falls $x$ kleiner ist als alle Elemente in $A$, so behauptet das Theorem, dass binarySearch den Wert $-1$ zurückgibt, weil ja per Konvention $A[-1] = -\infty$ gilt und somit $A[-1] = -\infty \lt x \lt A[0]$. Falls $x$ größer als alle Elemente in $A$ ist, soll binarySearch den Wert $n-1$ zurückgeben, da dann $A[n-1] \lt x \lt A[n] = \infty$ gilt. Falls $A$ ein leeres Array ist, also $n=0$ gilt, dann ist $\{-1,\dots,n-1\} = \{-1\}$ und es $-1$ ist die korrekte Antwort, weil $-\infty = A[-1] \lt x \lt A[0] = A[n]= \infty$ ist. Falls $x$ nicht im Array ist, gilt $A[j] \lt x \lt A[j+1]$, was dann auch zertifiziert, dass $x$ nicht im Array vorhanden ist.

Beweis des Theorems. Wir formulieren eine Schleifeninvariante; das ist eine Behauptung über den Zustand der Variablen im Code. Wir zeigen, dass die Schleifeninvariante nach $i$ Schleifendurchläufen gilt; $i=0$ heißt dabei vor dem ersten Schleifendurchlauf; dann zeigen wir, dass aus ihrer Gültigkeit in Zeile 9 die Korrektheit folgt, also die Behauptung im Theorem. Um die Schleifeninvariante zu formulieren, definieren wir

\begin{align} l_i := \textnormal{der Wert von $l$, nachdem $i$ Schleifendurchläufe durchlaufen worden sind} \label{def-l-i}\\ u_i := \textnormal{der Wert von $u$, nachdem $i$ Schleifendurchläufe durchlaufen worden sind} \ . \label{def-u-i} \end{align}

Es gilt also $l_0 = -1$ und $u_0 = n$.

Schleifeninvariante. Es gelten \begin{align*} l_i & \lt u_i \textnormal{ und } \\ A[l_i] & \leq x \lt A[u_i] \ , \end{align*} für jedes $i$, sofern die Schleife mindestens $i$ mal durchlaufen wird.

Beweis. Wir verwenden Induktion über $i$. Im Basisfall haben wir $i=0$ und befinden wir uns vor dem ersten Schleifendurchlauf. Es gelten $l_0 = -1$ und $u_0 = n$; somit gilt schon einmal $l_0 \lt u_0$ (auch falls $n=0$!); da nach Konvention $A[l_0] = -\infty$ und $A[u_0] = +\infty$ gilt, gilt auch $A[l_0] \leq x \lt A[u_0]$. Die Invariante gilt also für $i=0$.

Sei nun $i \geq 0$. Wir nehmen per Induktionshypothese an, dass die Invariante nach dem $i$-ten Durchlauf, also zu Beginn des $(i+1)$-ten gilt, und müssen zeigen, dass sie auch nach dem $(i+1)$-ten gelten wird. Wir können nach Induktionshypothese also davon ausgehen, dass

\begin{align*} l_{i} & \lt u_i \textnormal{ und } \\ A[l_i] & \leq x \lt A[u_i] \ , \end{align*}

gelten. Nun sei $m := \floor{\frac{l_i + u_i}{2}}$. Da es einen $i$-ten Durchlauf gibt, gilt $u_i - l_i \geq 2$ und somit $l_i \lt m \lt u_i$. Wie in Zeile 5 des Codes müssen wir zwei Fälle unterscheiden:

Fall 1: $A[m] \leq x$. In diesem Fall gelten dann per Zeile 6 des Codes $l_{i+1} = m$ und $u_{i+1} = u_i$ und somit

\begin{align*} A[l_{i+1}] & \leq x \tag{Annahme dieses Falles } \\ x & \lt A[u_{i+1}] \tag{weil $u_{i+1} = u_i$ und Induktionshypothese} \\ l_{i+1} & \lt u_{i+1} \tag{weil $l_{i+1} = m \lt u_i$.} \end{align*}

Die Invariante gilt also auch für $i+1$.

Fall 2: $A[m] \gt x$. In diesem Fall gelten dann per Zeile 8 des Codes $l_{i+1} = l_i$ und $u_{i+1} = m$ und somit

\begin{align*} A[l_{i+1}] & \leq x \tag{weil $l_{i+1} = l_i$ und Induktionshypothese} \\ x & \lt A[u_{i+1}] \tag{Annahme dieses Falles } \\ l_{i+1} & \lt u_{i+1} \tag{weil $l_{i+1} = m \lt u_i$.} \end{align*}

Per Induktion gilt die Behauptung für alle $i \geq 0$, sofern es überhaupt einen $i$-ten Schleifendurchlauf gibt. $\square$

Aus dem Beweis der Invariante folgt auch, dass $u_{i+1} - l_{i+1} \leq u_i - l_i - 1$; der Abstand schrumpft also in jedem Schritt um mindestens $1$. Daher gibt es nur endlich viele Durchläufe, sagen wir $t$ viele. Nach dem $t$-ten Durchlauf gelten:

\begin{align*} u_t = l_t + 1 \tag{weil sonst die Schleife weiterlaufen würde } \\ A[l_t] \leq x \lt A[u_t] \tag{wegen der Invariante} \end{align*}

Für den return-Wert $j = l_t$ gilt also $A[j] \leq x \lt A[j+1]$, wie behauptet.$\square$

Theorem (Laufzeit der binären Suche). Auf einem Array der Länge $n$ tätigt binarySearch(array,x) maximal $\ceil{\log (n+1)}$ Schleifendurchläufe.

Der etwas sperrige Ausdruck $\ceil{\log (n+1)}$ hat eine ganz einfache Interpretation: es ist die Anzahl der Bits in der Binärdarstellung von $n$ (wenn wir $0$ als leeren String mit null Bits darstellen).

Beweis. Wir betrachten den Wert $d_i := u_i-l_i-1$ und wie er sich im Verlauf der Ausführung verändert; die Werte $l_i$ und $u_i$ sind wie oben in (\ref{def-l-i}) und (\ref{def-u-i}) im Beweis des vorherigen Theorems definiert.

Behauptung. Sei $i \geq 0$. Wenn es überhaupt einen $(i+1)$-ten Schleifendurchlauf gibt, dann gilt

\begin{align*} d_{i+1} \leq \floor{\frac{d_i}{2} } \end{align*}

Beweis. Betrachten wir wieder die if-Bedingung in Zeile 5 und die beiden Möglichkeiten. Wenn Zeile 6 aufgerufen wird, dann gilt

\begin{align*} l_{i+1} & = \floor{\frac{l_i + u_i}{2}} \\ u_{i+1} & = u_i \end{align*}

und somit

\begin{align} u_{i+1} - l_{i+1} - 1 & = u_i - \floor{\frac{l_i + u_i}{2}} - 1 \label{difference-case-1} \end{align}

Falls Zeile 8 aufgerufen wird gilt

\begin{align*} l_{i+1} & = l_i\\ u_{i+1} & = \floor{\frac{l_i + u_i}{2}} \end{align*}

und somit

\begin{align} u_{i+1} - l_{i+1} - 1 & = \floor{\frac{l_i + u_i}{2}} - l_i - 1 \label{difference-case-2} \end{align}

Nun ist immer $(\ref{difference-case-2}) \leq (\ref{difference-case-1})$, denn:

\begin{align*} (\ref{difference-case-2}) & = \floor{\frac{l_i + u_i}{2}} - l_i - 1\\ & \leq \frac{l_i + u_i}{2} - l_i - 1 \\ & = u_i - \frac{u_i + l_i}{2} - 1 \\ & \leq u_i - \floor{\frac{u_i + l_i}{2}} - 1 = (\ref{difference-case-1}) \ . \end{align*}

Es genügt also zu zeigen, dass $(\ref{difference-case-1}) = \floor{\frac{u_i -l_i}{2} }-1$ ist. Zeigen wir das. Wir unterscheiden zwei Fälle: ob $u_i + l_i$ (und ebenso $u_i - l_i$) gerade oder ungerade ist.

Fall 0: $u_i + l_i$ ist gerade. Dann ist

\begin{align*} (\ref{difference-case-1}) & = u_i - \floor{\frac{u_i + l_i}{2}} - 1 = u_i- \frac{u_i + l_i}{2} - 1 \\ & = \frac{u_i - l_i}{2} - 1 = \floor{\frac{u_i - l_i-1}{2}} \tag{da $u_i-l_i-1$ ungerade ist} \end{align*}

Fall 1: $u_i + l_i$ ist ungerade. Dann ist

\begin{align*} (\ref{difference-case-1}) & = u_i - \floor{\frac{u_i + l_i}{2}} - 1 = u_i- \frac{u_i + l_i-1}{2} - 1 \\ & = \frac{u_i - l_i-1}{2} - 1 = \floor{\frac{u_i - l_i-1}{2}} \tag{da $u_i - l_i - 1$ gerade ist} \end{align*}

In jedem Fall gilt also $d_{i+1} = u_{i+1} - l_{i+1} - 1 \leq (\ref{difference-case-1}) = \floor{\frac{u_i - l_i-1}{2}}$ und somit haben wir die Behauptung. $\square$

Rekapitulieren wir: der Wert $d_i$ ist am Anfang, also für $i=0$, gleich $n - (-1) - 1 = n$. In jedem Schritt halbiert und rundet er sich ab:

\begin{align*} d_{i+1} \leq \floor{\frac{d_i}{2}} \ . \end{align*}

Wenn er nach $t$ Schritten den Wert $0$ erreicht, gilt $d_t = u_t - l_t - 1 = 0$, also $u_t - l_t = 1$, und die Schleife bricht ab. Die Zahl $t$ der Schleifendurchläufe ist also gleich der Anzahl der Halbierung-und-Abrundungsschritte, die der Wert $d_i$ durchläuft. Die Funktion $f: x \mapsto \floor{\frac{x}{2}}$ hat eine ganz einfache Interpretation:

Beobachtung. Sei $x \in \N^+$ eine positive ganze Zahl. Dann erhalten wir $f(x)$, indem wir $x$ in Binärdarstellung schreiben und die rechteste Stelle löschen. In diesem Zusammenhang stellen wir die Zahl $0$ als leeren String dar, also als Bitstring der Länge null.

Wie oft müssen wir, beginnend bei $n$, die rechteste Stelle löschen, bis wir eine leere Zahl (also die Null) erhalten? So oft, wie $n$ Stellen hat. Wie viele Stellen hat die Zahl $n$ in Binärdarstellung? Genau $\ceil{\log_2(n+1)}$ viele (wobei $0$ durch den leeren String repräsentiert wird). Wir folgern: auf einem Array der Länge $n$ startet der Wert $d_i$ bei $d_0 = n$ und es gilt $d_{i+1} \leq f(d_i)$. Die Länge der Binärdarstellung von $d_i$ schrumpft also in jedem Schleifendurchlauf um mindestens $1$, und somit haben wir nach höchstens $t = \ceil{\log_2(n+1)}$ Durchläufen $d_t = 0$ und somit das Ende erreicht. $\square$

Als Beispiel nehmen wir die Binärzahl $(111001)_2 = (57)_{10}$. Wenn wir $f$ wiederholt anwenden, erhalten wir

\begin{align*} 111001 \stackrel{f}{\mapsto} 11100 \stackrel{f}{\mapsto} 1110 \stackrel{f}{\mapsto} 111 \stackrel{f}{\mapsto} 11 \stackrel{f}{\mapsto} 1 \stackrel{f}{\mapsto} 0 \end{align*}

was in Dezimalschreibweise der Halbier-und-Abrunde-Sequenz

\begin{align*} 57 \mapsto 28 \mapsto 14 \mapsto 7 \mapsto 3 \mapsto 1 \mapsto 0 \end{align*}

entspricht. Auf einem Array mit $57$ Elementen tätigt binarySearch also maximal sechs Schleifendurchläufe.

Der Ausdruck $\ceil{\log_2 (n+1)}$ hat noch eine andere Interpretation: die binäre Suche, so wie wir sie im Moment verstehen, erhält mit jeder Anfrage eine binäre Antwort, nämlich kleiner gleich oder größer. Nach $k$ Anfragen ergibt sich also ein Muster aus $k$ Bits. Es gibt $2^k$ verschiedene solche "Bitmuster". Wenn unsere Strategie erfolgreich sein will, dann muss sie in der Lage sein, $n+1$ verschiedene Antworten zu geben, nämlich $-1, 0, ..., n-1$. Da identische Bitmuster identische Antworten geben, muss es mindestens $n+1$ verschiedene Bitmuster geben, also

\begin{align*} 2^k \geq n+1 \end{align*}

was genau $k \geq \ceil{\log_2 (n+1)}$ bedeutet.

Implementierung in Python

Schreiben wir nun eine kleine Funktion in Python, die binäre Suche implementiert.

def binarySearch (data, x):
    lower = -1
    upper = len(data)  
    while (upper - lower > 1):
        lookup = (upper + lower) // 2
        if (data[lookup] <= x):
            lower = lookup 
        else:
            upper = lookup 
        # end if  
    return lower

Python-Programme sind oft sehr kurz, weil Sie im Gegensatz zu Java keine großen Typendeklarationen machen müssen und Fehlerbehandlung gänzlich ausblenden können. Daher eignet sich Python wunderbar, um Algorithmen quick and dirty zu implementieren. Verwenden Sie aber Python bitte nicht, um die Steuerungssoftware eines Atomkraftwerks zu schreiben!

Übungsaufgabe Kopieren Sie den Python-Code in eine Datei binarySearch.py und speichern Sie die Datei in einem sinnvollen Verzeichnis, beispielsweise home/AuK/code/binarySearch/. Speichern Sie auch englishVocabulary.py dort ab. Fügen Sie die folgende Zeile an den Anfang der Datei binarySearch.py ein:

from englishVocabulary import wordlist_sorted, wordlist_unsorted

Öffnen Sie eine Konsole und starten Sie das Python-Programm im Repl-Modus:

~/AuK/code/binarySearch $ python3 -i binarySearch      
binarySearch(wordlist_sorted, "yak")
57885
wordlist_sorted[57885]
'yak'

Geben Sie per Hand ein sortiertes Array ein, also beispielsweise data = [1,4,9,16,25] und spielen damit rum.

Testen Sie Grenzfälle wie Suchwörter, die kleiner sind als alle Einträge oder solche, die größer sind als alle. Was geschieht bei leeren Arrays?

Übungsaufgabe Schreiben Sie eine Funktion linearSearch, die das Array in linearer Suche durchgeht und dadurch auch auf unsortierten Arrays funktioniert.

Testen Sie sie auf der unsortierten Wortliste wordlist_unsorted, die ebenfalls englishVocabulary.py definiert ist.

Laufzeit mesen

Mit Python können Sie recht einfach die Laufzeit Ihrer Funktionen messen. Um das Ihnen noch leichter zu machen, habe ich ein kleines Modul timeMyPrograms.py geschrieben. Kopieren Sie die Datei in Ihren Verzeichnis .../code/binarySearch und fügen Sie oben in binarySearch.py die Code-Zeile

from timeMyPrograms import *

ein. Dann können Sie die Laufzeit wie folgt messen:

~/AuK/code/binarySearch $ python3 -i binarySearch
binarySearch(wordlist_sorted, "processor")
39136
measure_alg(binarySearch, wordlist_sorted, "processor")
1.2775002687703818e-05

Ganz allgemein können Sie mit measure_alg(alg, p_1, p_2, ..., p_n) die Laufzeit des Aufrufs von alg(p_1, p_2, ..., p_n) empirisch messen. Beachten Sie, dass die Zahl 1.2775002687703818e-05 die Floating-Point-Schreibweise ist für

\begin{align*} 1.2775002687703818 \times 10^{-5} \ . \end{align*} Die Laufzeit beträgt also eine gute hunderttausendstel Sekunde.

Übungsaufgabe Messen Sie empirisch die Laufzeit Ihrer Implementierungen von binarySearch und linearSearch. Um welchen Faktor unterscheiden sie sich?

Implizite binäre Suche

Binäre Suche taucht auch oft auf, ohne dass explizit ein Array vorliegt. Beispielsweise, wenn wir die ganzzahlige Wurzel einer Zahl berechnen wollen:

\begin{align*} {\rm intSqrt} : \mathbb{N} & \rightarrow \mathbb{N} \\ n & \mapsto \floor{\sqrt{n}} \end{align*}

Wir wollen hier explizit nicht auf die bereits vorhandene Bibliotheksfunktion math.sqrt zurückgreifen. Diese arbeitet insbesondere mit Floating-Point-Zahlen und liefert daher auch schnell falsche Ergebnisse:

~/AuK/code/binarySearch $ python3 -i binarySearch      
def sqrtInt(n): return math.floor(math.sqrt(n))                        
sqrtInt(16):
4
n = 3**40
sqrt(n*n) - n
-33 # Ouch!

Wir müssen es also selbst implementieren. Denken wir nach: ${\rm intSqrt}(n)$ ist die größte ganze Zahl $k$ mit $k^2 \leq n$. Daher der folgende Algorithmus:

def intSqrt(n):
    k = 0
    while (k*k <= n):
        k = k+1
    return k-1

Übungsaufgabe Experimentieren Sie mit der Funktion intSqrt. Wie weit kommen Sie mit vertretbarer Laufzeit? Was ist der Zusammenhang zwischen $n$ und der Laufzeit von intSqrt?

Was ist die Größe einer ganzen Zahl?

Die Laufzeit von intSqrt(n) ist ungefähr proportional zu der Anzahl der Schleifendurchläufe und somit zu $\sqrt{n}$ selbst. Das klingt jetzt gar nicht so schlecht. Nehmen wir aber als Beispiel einmal die Zahl $n := 2^{60}$. Offensichtlich ist $\sqrt{n} = 2^{30}$. Dies ist ungefähr eine Milliarde. Unser Algorithmus braucht also eine Milliarde Schleifendurchläufe. Auf einem schnellen Rechner und mit der C-Implementierung ginge das vermutlich in erträglicher Zeit über die Bühne. Ein zeitgenössisches Macbook (Stand Herbst 2023) mit einem Apple M2 Pro Prozessor hat 12 CPU-Kerne, von denen jeder bis zu 3,5 GHz hat. Seien wir unrealistisch optimitisch und nehmen an, ein Schleifendurchlauf von intSqrt bräuchte einen Prozessortakt, und darüberhinaus ist alles perfekt parallelisierbar (also auf die 12 CPU-Kerne) verteilbar, so dass das Macbook pro Sekunde $12 \cdot 3.5 \cdot 10^9 = $ 42 Milliarden Durchläufe schafft.

In diesem (unrealistisch optimistischen) Szenario würde intSqrt(2**80) also $\frac{\sqrt{2^{80}}}{42 \cdot 10^9} \approx 31$ Sekunden dauern. intSqrt(2**100) bereits tausendmal so lange, also fast einen halben Tag. Ist das gerechtfertigt? Ist 2**100 eine "große" Zahl? Fragen wir Python:

2**100                        
1267650600228229401496703205376

Das passt wunderbar auf eine Zeile. Gemessen an der Anzahl an Stellen, die wir brauchen, um diese Zahl zu repräsentieren, ist sie recht klein. Im Allgemeinen bemisst man die Größe einer Zahl (im Kontext von Algorithmen) als ihre Bitlänge, also die Anzahl der Bits in ihrer Binärdarstellung. Wie bereits weiter oben diskutiert hat die Zahl $n$ die Bitlänge

\begin{align*} \ceil{\log_2 (n+1)} \end{align*}

Anders herum gesagt: eine $k$-stellige Zahl $n$ (in Bits) ist mindestens $2^{k-1}$ und höchstens $2^{k} - 1$. Die Funktion intSqrt(n) benötigt also mindestens

\begin{align*} \sqrt{2^{k-1}} = 2^{\frac{k-1}{2}} \end{align*}

Schleifendurchläufe. Somit ist die Laufzeit exponentiell in der Bitlänge $k$. Intuitiver ausgedrückt: wenn wir die Bitlänge um 2 Bits erhöhen, dann verdoppelt sich die Laufzeit.

Quadratwurzel mit binärer Suche

Wenn wir ein Array mit den Quadratzahlen $A = [0, 1, 4, 9, 16, ..., m^2]$ gegeben haben, dann können wir für eine Eingabezahl $0 \leq n \leq k^2 $ per binärer Suche das größte $k$ lokalisieren, für das $A[k] \leq n$ gilt. Da $A[k] = k^2$, so gilt dann eben auch $k = {\rm sqrtInt} (n)$.

~/AuK/code/binarySearch $ python3 -i binarySearch.py                        
array = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100]                        
binarySearch(array, 48)
6

Wir können also mittels binärer Suche die Quadratwurzel berechnen. Natürlich müssen (dürfen) wir das Array $A$ nicht explizit konstruieren (das würde zu viel Zeit und Platz beanspruchen). Wir müssen also eine implizite binäre Suche durchführen, in welcher der Array-Zugriff

        if (data[lookup] <= x):

durch einen Funktionsaufruf ersetzen.

Übungsaufgabe

Schreiben Sie in Python eine Funktion intSqrt (n), die die Funktion $$ n \mapsto \floor {\sqrt{n}} $$ berechnet. Ihre Funktion soll ohne Probleme die Quadratwurzel hundertstelliger Zahlen berechnen können.

Übungsaufgabe Messen Sie die Laufzeit Ihres Algorithmus mit measure_alg (intSqrt, 2**100), beispielsweise.

Legen Sie eine Tabelle an: wie entwickelt sich die empirisch gemessene Laufzeit mit der Bitlänge der Eingabezahl? Tip: Sie müssen schon sehr große Zahlen eingaben (tausendstellige, zehntausendstellige), um die Laufzeit zu "spüren".

Wenn Sie die Bitlänge verdoppeln, wie verändert sich die Laufzeit?

Übungsaufgabe Schreiben Sie eine Funktion, die Nullstellen von Polynomen von ungeradem Grad finden kann, also zum Beispiel

\begin{align*} x^5 - x + 1 \end{align*}

Das Polynom kann z.B. als Array von Koeffizienten gegeben sein. Obiges wäre zum Beispiel [1,-1, 0, 0, 0, 1]. Da es sich bei der Wurzel im Allgemeinen um eine irrationale Zahl handelt, können wir nur Näherungswerte angeben. Wir brauchen also einen Präzisionsparameter $\epsilon$. Schreiben Sie eine Funktion find_root(polynomial, epsilon), die eine Zahl $x$ zurückgibt, so dass $p(x)$ und $p(x + \epsilon)$ umgekehrte Vorzeichen haben, formal also dass

\begin{align*} p(x) \cdot p(x + \epsilon) \leq 0 \end{align*}

gilt.

Untere Schranken

Ü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).