Zu zweit oder dritt: Eine Person wählt in einem Wörterbuch oder Lexikon heimlich einen Eintrag, der auf einer Seite rechts oben steht. Das Buch wird geschlossen und eine andere Person versucht mit möglichst wenigen Suchschritten (1x Blättern ist ein Schritt), den Begriff zu finden. Es ist dabei verboten, auf die Markierungen mit den Anfangsbuchstaben an der Seite des Buches zu schauen.

Überlegt euch verschiedene Strategien, wie ihr vorgehen könnt. Welche Strategie benötigt die wenigsten Schritte?

• Wie oft musst du blättern (bzw. die Seiten aufteilen), bis du das Wort gefunden hast?
• Wie oft müsstest du durchschnittlich mit der linearen Suche blättern?
• Wieviele Positionen (Finger zwischen den Seiten) musst du dir merken?

Ist ein Datensatz nicht sortiert, macht eine lineare Suche Sinn. Ist dieser aber bereits sortiert, so gibt es viel effizientere Suchalgorithmen, wie die hier beschriebene binäre Suche:

Wir teilen den Suchbereich ungefähr in der Mitte. Ist der Begriff zufälligerweise gleich dort, haben wir den Eintrag gefunden; ist der Begriff kleiner als das gefundene Element, suchen wir in der ersten Hälfte, sonst in der zweiten Hälfte weiter, bis genau ein einziges Element übrig bleibt. An dieser Stelle befindet sich der gesuchte Begriff, wenn er überhaupt vorhanden ist. Falls nicht, würde er an dieser Stelle eingefügt werden.

Bei der Suche im Wörterbuch suchen wir zu Beginn nur die richtige Seite - wir teilen den Suchbereich, indem wir die Mitte der verbleibenden Seiten wählen und den ersten Eintrag der Seite anschauen. Sind wir auf der richtigen Seite, wiederholen wir dasselbe mit den einzelnen Einträgen.

1. Eine Broschüre hat 7 Seiten und du möchtest mithilfe der binären Suche eine bestimmte Seite finden. Wie viele Seiten musst du maximal aufschlagen? Tipp: Zeichne auf einem Blatt vor dir 7 Striche, die die Seiten repräsentieren.
2. Wie sieht es mit einer Broschüre mit 15 oder 31 Seiten aus? Wie mit einem Buch mit 255 Seiten?
3. Erkennst du einen (mathematischen) Zusammenhang zwischen der Anzahl Seiten und der Anzahl Aufschlagen?
4. Stelle dir vor, es gäbe ein Telefonbuch für alle 8 Milliarden Menschen, wobei jede Person eine einzelne Seite hätte. Ist eine Seite 0.1mm dick, so wäre dieses Telefonbuch ca. 800km dick, was ungefähr der Distanz Romanshorn - London entspricht. Wie viele Seiten musst du maximal aufschlagen, um eine beliebige Person auf einer einzelnen Seite zu finden?

Binäre Suche ist also ein äusserst leistungsfähiger Algorithmus, um in einer sortierten Liste ein gewünschtes Element zu finden. Der Suchaufwand wächst nur logarithmisch: Verdoppelt sich die Seitenzahl, so wächst der Aufwand nur um eine Halbierung; bei der linearen Suche würde sich der Aufwand auch verdoppeln.

Allerdings funktioniert die Binärsuche nur, wenn die Sortierung unserem Such-Schlüssel entspricht. Den Namen zu einer gewünschten Telefonnummer zu finden, ist beispielsweise im klassischen Telefonbuch nicht möglich: die Nummern sind in keiner bestimmten Reihenfolge, wir müssten das ganze Telefonbuch linear durchsuchen, um die gewünschte Nummer zu finden. tel.search.ch verwendet dazu einen zweiten, invertierten Index, bei dem die Namen nach Telefonnnummer sortiert abgespeichert werden.

Komplettiere folgenden Code und teste ihn aus. Wir merken uns zwei Variablen, links und rechts, die den Suchbereich abstecken: links ist die Position des kleinsten Elements, rechts die Position des grössten Elements, das noch in Frage kommt. Zu Beginn ist links natürlich null, und rechts ist der Index des letzten Elements (also len(l) - 1).

Mehr Hinweise

print(11 // 2)
>>> 5

Was passiert, wenn du statt nach Telefonnummern statt nach Namen suchst? Funktioniert die Binärsuche? Weshalb nicht? Was müssten wir ändern, damit sie funktioniert?

In Aufgabe A6 wird die Funktion für die lineare Suche abgeändert für den Fall, dass das gesuchte Element mehrmals in der Liste vorkommt. Die neue Funktion gibt nicht nur die erste Position des gesuchten Elements zurück, sondern sie gibt eine Liste mit allen Positionen zurück, in denen das gesuchte Element vorkommt. Erstelle eine Funktion binary_search2(li, el) welche ebenso funktioniert. Du kannst natürlich davon ausgehen, dass die Liste sortiert ist. Teste deine Funktion zum Beispiel wie folgt:

def binary_search2(li, el):
   # dein Code hier!
 
my_list = ['A','A','C','E','E','E','E','E','G','G','G','G']
print(binary_search2(my_list,'A')) # Erwartete Ausgabe: [0, 1]
print(binary_search2(my_list,'B')) # Erwartete Ausgabe: None
print(binary_search2(my_list,'C')) # Erwartete Ausgabe: [2]
print(binary_search2(my_list,'D')) # Erwartete Ausgabe: None
print(binary_search2(my_list,'E')) # Erwartete Ausgabe: [3, 4, 5, 6, 7]
print(binary_search2(my_list,'F')) # Erwartete Ausgabe: None
print(binary_search2(my_list,'G')) # Erwartete Ausgabe: [8, 9, 10, 11]
print(binary_search2(my_list,'H')) # Erwartete Ausgabe: None

def binary_search2(li, el):
    results = []
    left = 0
    right = len(li)-1
    while left <= right:
        mid = (left + right) // 2
        if li[mid] == el:
            while li[mid] == el:
                mid -= 1
            mid += 1
            while mid < len(li) and li[mid] == el:
                results.append(mid)
                mid += 1
            return results
        elif li[mid] < el:
            left = mid + 1
        else:
            right = mid -1
    return None

Weiter zu Sortieren