Binäre Suche

Aufgabe

Warum das so ist, werden wir uns nun gemeinsam anschauen. Wenn wir einfach einen Tag raten würden, würden wir in 364 Fällen falsch liegen und nur einmal richtig. Das klingt also nach keiner guten Strategie. Wir müssen also versuchen, das Problem, einen von 365 Tagen zu raten, irgendwie verkleinern. Dazu fragen wir, ob der Geburtstag vor oder nach dem 1. Juli liegt, also quasi ob er in der ersten Hälfte des Jahres liegt. Ist die Antwort "Ja", wissen wir, dass der Geburtstag im Januar bis Juni liegt, und bei einem "Nein", dass er im Juli bis Dezember liegt. Damit haben wir die Anzahl an möglichen Tagen bereits halbiert. Wir können nun wieder fragen, ob der Geburtstag in der ersten Hälfte des Halbjahres liegt. Damit haben wir die Anzahl an möglichen Tagen nochmal halbiert. Das wiederholen wir so lange, bis wir nur noch einen Tag übrig haben. Das ist dann der gesuchte Geburtstag. Wir haben also jeweils das Problem, einen von n Tagen zu raten, auf das Problem, einen von n/2 Tagen zu raten, zurückgeführt. Wenn wir nun mitzählen, wie oft wir die möglichen Tage halbieren bis wir bei nur noch einem einzigen Tag liegen, kommen wir auf 9.

Das kann man natürlich auch mathematisch berechnen. Und zwar mit dem Logarithmus $log_2(n)$. Der sagt uns nämlich, wir oft wir die 2 mit sich selbst multiplizieren müssen, um auf n zu kommen, löst also die Gleichung $2^x = n$. So können wir auch herausfinden, wie oft wir n halbieren müssen, um auf 1 zu kommen. Mit acht Fragen können wir $2^8 = 256$ Tage und mit neun Fragen $2^9 = 512$ Tage abdecken. Da wir aber nur 365 Tage haben, reichen uns neun Fragen immer aus. Rechnen wir das Ganze mal in einem Beispiel durch:

(Das folgende Beispiel könnte auch als interaktive Aufgabe gestaltet werden, bei der man die Fragen selbst stellt oder die Antworten eingibt.)

Was hat jetzt aber die Frage nach dem Geburtstag einer Person mit Informatik zu tun? Die Strategie, die wir hier angewendet haben, nennen wir Binäre Suche. Sie ist eine sehr wichtige Strategie in der Informatik, um in sortierten Daten nach einem bestimmten Element zu suchen. Hier suchen wir unter den verschiedenen Geburtstagen den einen gesuchten. Die Binäre Suche ist ein gutes Beispiel für ein Problem, das wir rekursiv lösen können. Wir können die Suche nämlich immer wieder auf eine kleinere Version des Problems zurückführen. Die Suche ist binär (von lateinisch bina "doppelt, paarweise"), weil wir die Daten immer in zwei Teile teilen.

Normalerweise geben Suchalgorithmen True oder False zurück, jenachdem ob das Element gefunden wurde oder nicht. Das Geburtstagsproblem ist zwar sehr anschaulich, natürlich ist das gesuchte Element hierbei aber immer in der Liste, das heißt der Algorithmus würde immer True zurückgeben. Deshalb betrachten wir ab jetzt tatsächlich Binäre Suche als das Problem, das wir rekursiv lösen wollen. Genauso wie eben fragen wir stets, ob das gesuchte Element kleiner oder größer-gleich ein Element, welches in der Mitte der (sortierten) Elemente, ist liegt. Fangen wir mit etwas Pseudocode an:

def binary_search(liste, element):
    # Basisfall: In einer leeren Liste können wir das Element nicht finden
    if (len(liste) == 0):
        return False 
    else:
        # Berechne mittleres Element
        mitte = len(liste) // 2 # // ist die Division, die immer abrundet
        mittleres_element = liste[mitte]

        # Überprüfe, ob das mittlere Element das gesuchte Element ist
        if (mittleres_element == element):
            return True
        # Überprüfe, ob das gesuchte Element kleiner als das mittlere Element ist
        elif (element < mittleres_element):
            # Suche in der ersten Hälfte
        else:
            # Suche in der zweiten Hälfte

Mithilfe dieser Funktion wird also das Problem verkleinert (circa halbiert). Jetzt müssen wir noch in jenachdem der ersten oder zweiten Hälfte weitersuchen. Hier kommt die Rekursion ins Spiel: wir erinnern uns an das Prinzip der Magie der Rekursion: wir nehmen an, dass die Funktion für das kleinere Problem bereits funktioniert und rufen die Funktion binary_search rekursiv auf. Das Ergebnis des rekursiven Aufrufs ist dann die Antwort auf die Frage, ob das Element in dem jeweiligen Teilbereich enthalten ist.

Aufgabe

Wenn wir uns die Länge der Liste in den oberen Knoten einmal genau anschauen und beobachten, wie sie sich in jedem Rekursionsschritt verändert, sehen wir, dass sie sich (ungefähr) halbiert. Daraus können wir ableiten, wie viele Rekursionschritte wir benötigen, um in einer $n$ großen Liste ein Element zu suchen. Und zwar genau $log_2(n)$ Schritte, da wir ja genau so oft die Liste halbieren müssen, bis wir bei einer Liste der Länge 1 angekommen sind. Wir sagen deshalb, dass die Funktion logarithmische Laufzeit zur Länge der Liste hat.