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. Wie viele Seiten musst du maximal aufschlagen, um eine beliebige Person 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

binaere_suche.py

def binary_search(l, v):
    """Gibt den Index des gesuchten Elements in l zurück, None,
       wenn das Element nicht existiert."""
    links = 0
    rechts = len(l) - 1
    while links <= rechts:
        # TODO: Dein Code hier!
        pass
    return None
 
# TEST YOUR FUNCTION
print(binary_search(['A','C','D','G','J','N','Q','X'],'B')) # output must be: None
print(binary_search(['A','C','D','G','J','N','Q','X'],'A')) # output must be: 0
print(binary_search(['A','C','D','G','J','N','Q','X'],'C')) # output must be: 1
print(binary_search(['A','C','D','G','J','N','Q','X'],'D')) # output must be: 2
print(binary_search(['A','C','D','G','J','N','Q','X'],'G')) # output must be: 3
print(binary_search(['A','C','D','G','J','N','Q','X'],'J')) # output must be: 4
print(binary_search(['A','C','D','G','J','N','Q','X'],'N')) # output must be: 5
print(binary_search(['A','C','D','G','J','N','Q','X'],'Q')) # output must be: 6
print(binary_search(['A','C','D','G','J','N','Q','X'],'X')) # output must be: 7
print(binary_search(['A','C','D','G','J','N','Q','X'],'Z')) # output must be: None

Kannst du nun die Funktion für die binäre Suche selbständig, also möglichst ohne nachschauen schreiben und diese auch verwenden, um in Listen zu suchen? Versuche es:

• Erstelle eine neue, leere Python-Datei und speichere sie (Name z.B.: aufgabe_b4.py) im gleichen Ordner wie die Datei null79.py.
  • Alternative: verwende WebtigerPython mit der bereits hinterlegten Datei.
• Importiere die das Modul null79, die du schon in Aufgabe A3 verwendet hast (from null79 import names, numbers).
• Schreibe selbständig deine Funktion binary_search(l, v): Sie soll die Position von v in der Liste l zurückgeben. Wenn nichts gefunden wird, soll die Funktion None zurückgeben.
• Definiere unter einer Variable namens name den gesuchten Namen, also Lyanna.
• Jetzt suchst du mit index = binary_search(names, name) nach dem Index von name in der Liste names.
• Unter dem gleichen Index findest du in numbers die dazugehörige Telefonnummer.
• Gib einen Satz im Format Die Telefonnummer von ... ist ... aus.
• Dein Code sollte so aufgebaut sein, dass du nur die Variable name ändern musst, damit ein neuer, korrekter Satz ausgegeben wird.

from null79 import names, numbers
 
def binary_search(l, v):
    left = 0
    right = len(l) - 1
 
    while left <= right:
        middle = (left + right) // 2
        element = l[middle]
        if element == v:
            return middle  # Gefunden!
        if v < element:
            # Links weitersuchen
            right = middle - 1
        else:
            # Rechts weitersuchen
            left = middle + 1
 
    return None  # Nichts gefunden
 
name = 'Lyanna'
index = binary_search(names, name)
if index is None:
    print('Du weisch immer no nüt')
else:
    telnr = numbers[index]
    print('Die Nummer von ' + name + ' lautet ' + telnr + '!')

Vergleiche die lineare Suche mit der binären Suche. Hierzu kannst du von Aufgabe B4 ausgehen (unter neuem Namen speichern):

1. Behalte nur die Listen und die Definition der Funktion binary_search().
2. Ergänze die Datei um die Funktion linear_search(l, v) (am besten, du schreibst du sie selbst hin, anstatt sie zu kopieren).
3. Definiere eine neue Funktion stopwatch(algo, name). Sie hat zwei Argumente:
   1. algo ist der Name der Suchfunktion (Suchalgorithmus), die verwendet werden soll (also binary_search oder linear_search, ohne die Klammern des Funktionsaufrufs).
   2. name ist der Name, nach dem gesucht werden soll.
4. Die Funktion soll mit dem gewünschten Algorithmus im Telefonbuch suchen und die Zeit für die Suche messen (import time, siehe auch Aufgabe A5). Am Ende soll die Funktion einen Text in folgender Form ausgeben: „Die Telefonnummer von … lautet …. Die Suche dauerte … Sekunden.“
5. Rufe nun die Funktion vier mal auf: Für Annina und Lyanna – jeweils mit der linearen und mit der binären Suche.

from null79 import names, numbers
import time
 
def binary_search(l, v):
    left = 0
    right = len(l) - 1
 
    while left <= right:
        middle = (left + right) // 2
        element = l[middle]
        if element == v:
            return middle  # Gefunden!
        if v < element:
            # Links weitersuchen
            right = middle - 1
        else:
            # Rechts weitersuchen
            left = middle + 1
 
    return None  # Nichts gefunden
 
def linear_search(l, v):
    for i in range(len(l)):
        if l[i] == v:
            return i
    return None
 
def stopwatch(algo, name):
    start = time.time()
    index = algo(names, name)
    telnr = numbers[index]
    elapsed = time.time() - start
    print('Die Nummer von {0} lautet {1}! Die Suche dauerte {2:.2f}s.'.format(name, telnr, elapsed))
 
stopwatch(linear_search, 'Annina')
stopwatch(binary_search, 'Annina')
stopwatch(linear_search, 'Lyanna')
stopwatch(binary_search, 'Lyanna')

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

Bei der binären Suche gehen wir ja wie folgt vor:

1. Index in der Mitte des Suchintervalls wählen.
2. Element in der Mitte auslesen.
3. Ist element == suche sind wir fertig.
4. Andernfalls wiederholen wir die Suche mit einem kleineren Teilintervall (zurück zu Schritt 1):
   1. Ist suche < element, so ist das neue Suchintervall die linke Hälfte.
   2. Andernfalls ist element < suche, das neue Suchintervall ist die rechte Hälfte.

Schreibe eine neue Funktion, binaere_suche_rekursiv(l, suche, links, rechts). Die Funktion codiert die obigen Schritte - statt einer while-Schleife soll die Funktion sich im Schritt 4 selber wieder aufrufen. Dieses Verfahren heisst Rekursion. Was sind die Startparameter für links und rechts?

Rekursion eignet sich für viele Probleme, die sich mit Divide & Conquer (Teile & Herrsche) lösen lassen: Probleme, die wir für den trivialen Fall mit einem Element lösen können, und die wir effizient von einem grösseren in ein kleineres Problem überführen können.

Weiter zu Sortieren