2. Suchen und Sortieren

2.1 Binäre Suche

Dieses Teilkapitel überschneidet sich stark mit dem aus der Vorlesung Theoretischen Informatik. Dennoch habe ich es hierhin kopiert, da ja nicht gararntiert ist, dass alle Teilnehmer und Teilnehmerinnen dieses Kurses auch in TI waren.

Erinnern Sie sich noch an das hier?

Vielleicht sind Sie ja dafür tatsächlich zu jung. Es ist ein Telefonbuch. Wenn man eine Telefonnummer herausfinden will, zum Beispiel vom Kfz-Mechaniker Windisch aus Freudenberg, dann schaut man im Telefonbuch unter "W" nach und blättert. Und heute? Da benutzt man immer noch ein Telefonbuch. Dies ist dann aber elektronisch, und das Blättern tun auch nicht Sie, sondern ein Rechner (oder viele). Sie können zum Beispiel Das Telefonbuch verwenden oder eine Suchmaschine Ihrer Wahl.

Und ob Sie eine Telefonnummer suchen oder etwas ganz Anderes, ein Großteil von dem, was Rechner erledigen müssen, beinhaltet, irgendwo Inhalte aus einer riesigen Datenmenge rauszufischen. Grund genug, diesem Thema ein paar Vorlesungsstunden zu widmen.

Um konkret zu werden: in der Datei englishVocabulary.txt finden Sie eine Liste von über 50.000 englischen Wörtern. Schauen Sie nach. Fällt Ihnen etwas auf? Die Wörter sind aphabetisch sortiert. Das sollte uns bei der Suche helfen. Spielen Sie das folgende Spiel, in dem Sie auf den Screenshot klicken:

Demo 2.1.1 (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.

Abstraktion

Versuchen wir nun, 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]\le A[1]\le \cdots \le A[n-1]$. Lassen Sie sich von dem mathematischen Symbol $\le$ nicht täuschen. Es muss sich bei den Eleemnten $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{array}{}\text{(1)}& A[l]\le x<A[u]\end{array}$$ gilt. Wir wählen anfangs $l=-1$ und $u=n$, wobei wir die Konvention im Hinterkopf haben, dass $A[i]=-\mathrm{\infty }$ für $i<0$ und $A[i]=\mathrm{\infty }$ für $i\ge n$.

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

Der genaue Ausdruck $$ ist schwierig zu merken. Allerdings wird es einfacher, wenn Sie sich folgende Beobachtung einprägen:

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

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 Elm oder 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!

from englishVocabulary import wordlist_sorted, wordlist_unsorted

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

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

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:

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: $$ ist die größte ganze Zahl $$ mit $$. Daher der folgende Algorithmus:

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

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 $$ selbst. Das klingt jetzt gar nicht so schlecht. Nehmen wir aber als Beispiel einmal die Zahl $$. Offensichtlich ist $$. 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 $$ 42 Milliarden Durchläufe schafft.

In diesem (unrealistisch optimistischen) Szenario würde intSqrt(2**80) also $$ 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 $$ die Bitlänge

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

Schleifendurchläufe. Somit ist die Laufzeit exponentiell in der Bitlänge $$. 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 $$ gegeben haben, dann können wir für eine Eingabezahl $$ per binärer Suche das größte $$ lokalisieren, für das $$ gilt. Da $$, so gilt dann eben auch $$.

~/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 $$ 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.

Untere Schranken