Binärsuche

Zurück zu Lineare Suche

Weiter zu Sortieren

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.

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 binärer Suche den Begriff zu finden. Die erste Person antwortet bei jedem Versuch, ob das gesuchte Wort gefunden ist oder ob es vor- oder nach dem vorgeschlagenen Begriff kommt.

• Wie oft musst du durchschnittlich 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?

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(li) - 1).

Mehr Hinweise

print(11 // 2)
>>> 5

Vollständige Erklärung und Anleitung

binaere_suche.py

def binary_search(li, el):
    """Gibt den Index des gesuchten Elements in l zurück, None,
       wenn das Element nicht existiert."""
    links = 0
    rechts = len(li) - 1
    while links <= rechts:
        # 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 plz_data.py.
• Importiere die Datei plz_data.py, die du schon in Aufgabe A3 verwendet hast (import plz_data).
• Erstelle zwei Listen: postleitzahlen = plz_data.postleitzahlen() und ortschaften = plz_data.ortschaften().
• Erstelle nun selbständig deine Funktion binary_search(li, el): Sie soll die Position des Elements el in der Liste li zurückgeben. Wenn nichts gefunden wird, soll die Funktion None zurückgeben.
• Definiere unter einer Variable namens plz eine Postleitzahl, die es gibt.
• Jetzt suchst du mit deiner Funktion binary_search() nach dem Index von plz in der Liste postleitzahlen.
• Gib einen Satz im Format „Die Ortschaft mit der Postleitzahl … heisst … “ aus.
• Dein Code sollte so aufgebaut sein, dass du nur die Variable plz ändern musst, damit ein neuer, korrekter Satz ausgegeben wird.

import plz_data
 
postleitzahlen = plz_data.postleitzahlen()
ortschaften = plz_data.ortschaften()
 
def binary_search(li, el):
    left = 0
    right = len(li)-1
    while left <= right:
        mid = (left + right) // 2
        if li[mid] == el:
            return mid
        elif li[mid] < el:
            left = mid + 1
        else:
            right = mid -1
    return None
 
plz = 1234
ort = ortschaften[binary_search(postleitzahlen, plz)]
print("Die Ortschaft mit der Postleitzahl {} heisst {}".format(plz, ort))

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(li, el) (am besten, du schreibst du sie selbst hin, anstatt sie zu kopieren).
3. Definiere eine neue Funktion suche_ort_mit_zeitmessung(algo, plz). Sie hat zwei Argumente: algo ist der Name der Suchfunktion (Suchalgorithmus), die verwendet werden soll (also binary_search oder linear_search); plz ist die Postleitzahl, nach der gesucht werden soll. Die Funktion soll mit dem gewünschten Algorithmus den Ort 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 Ortschaft mit Postleitzahl … heisst …. Die Suche dauerte … Sekunden.“
4. Rufe nun die Funktion vier mal auf: Für die Postleitzahlen 1000 und 8590 – jeweils mit der linearen und mit der binären Suche.

import plz_data
import time
 
postleitzahlen = plz_data.postleitzahlen()
ortschaften = plz_data.ortschaften()
 
def linear_search(li, el):
    for i in range(len(li)):
        if li[i] == el:
            return i
    return None
 
def binary_search(li, el):
    left = 0
    right = len(li)-1
    while left <= right:
        mid = (left + right) // 2
        if li[mid] == el:
            return mid
        elif li[mid] < el:
            left = mid + 1
        else:
            right = mid -1
    return None
 
def suche_ort_mit_zeitmessung(algo, plz):
    start = time.time()
    ort = ortschaften[algo(postleitzahlen,plz)]
    elapsed = time.time()-start
    print("Der Ort mit Postleitzahl {} heisst {}. Die Suche dauerte {:.3f} s.".format(plz, ort, elapsed))
 
suche_ort_mit_zeitmessung(linear_search, 1000) # Messung 1: lineare Suche mit tiefer PLZ
suche_ort_mit_zeitmessung(linear_search, 8590) # Messung 2: lineare Suche mit hoher PLZ
suche_ort_mit_zeitmessung(binary_search, 1000) # Messung 3: binäre Suche mit tiefer PLZ
suche_ort_mit_zeitmessung(binary_search, 8590) # Messung 4: binäre Suche mit hoher PLZ

Was passiert, wenn du statt nach Postleitzahlen nach Orten 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 funktionert. 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