====== Binärsuche ======

Zurück zu [[gf_informatik:suchen_und_sortieren_2023#lineare_suche|Lineare Suche]]

Weiter zu [[gf_informatik:suchen_und_sortieren:sortieren|Sortieren]]

______

{{ :gf_informatik:binary_search.png?nolink&400| }}

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.
#### Aufgabe B1: Binäre Suche im Wörterbuch

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?

<nodisp 1>
++++Lösung|
  * In einem Band mit 1000 Seiten solltest du nach 10 Teilungen auf der richtigen Seite sein.
  * In einem Band mit 1000 Seiten müsste mit der linearen Suche durchschnittlich 500 Mal geblättert werden.
  * Zwei Positionen: Man merkt sich jeweils die obere und untere Grenze des Suchbereichs, während man in der Mitte aufschlägt.
++++
</nodisp>
#### Aufgabe B2: Binäre Suche berechnen

  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.
  1. Wie sieht es mit einer Broschüre mit 15 oder 31 Seiten aus? Wie mit einem Buch mit 255 Seiten?
  1. Erkennst du einen (mathematischen) Zusammenhang zwischen der Anzahl Seiten und der Anzahl Aufschlagen?
  1. 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?

<nodisp 1>
++++Lösung|

   1. Für **7** Seiten sind **3** Halbierungen nötig, bis nur noch eine Seite übrig bleibt. Das heisst, im schlechtesten Fall **3 mal aufschlagen**:
      1. Die mittlere (4.) Seite aufschlagen $\rightarrow$ eine Hälfte fällt weg, drei Seiten in der anderen Hälfte bleiben übrig.
      1. Die mittlere der drei Seiten aufschlagen $\rightarrow$ eine Hälfte fällt weg, eine Seite in der anderen Hälfte bleibt übrig.
      1. Zu dieser einen Seite blättern. 
   1. Für **15** Seiten sind **4** Halbierungen nötig. Bei **31** Seiten max. **5 mal blättern**. Und bei **255** Seiten max. **8 mal**.
   1. In einem Buch mit $2^n - 1$ Seiten musst du maximal $n$ mal blättern. Du hast Exponentialrechnung eventuell noch gar nicht in der Mathematik behandelt - aber du kannst dir vorstellen, dass die Seitenzahl sehr viel stärker wächst als die Anzahl Halbierungen.
   1. $2^{33}-1 = 8589934591$, also $33\times$ blättern.

++++
</nodisp>

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 [[https://www.equestionanswers.com/c/images/log2n.gif|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
.
#### Aufgabe B3: Binäre Suche in Python

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|
In der `while`-Schleife manipulieren wir nun diese Positionen, indem wir eine Position in der Mitte der beiden auswählen: `mitte = ...`. Das Element in der Mitte (`li[mitte]`) können wir nun mit dem gesuchten Element vergleichen. Was tun wir, wenn das Mitte-Element genau der Suche entspricht? Wenn das gesuchte Element kleiner oder grösser als das in der Mitte ist, müssen `links` oder `rechts` angepasst werden - aber wie genau?

Beachte:
  * Zeichne die Suche auf Papier auf, um keine Verwirrung mit den Positionen entstehen zu lassen.
  * Um eine Ganzzahl-Division (ohne Rest) durchzuführen, benützen wir in Python den `//` Operator:

<code python>
print(11 // 2)
>>> 5
</code>
++++

[[gf_informatik:suchen_und_sortieren::binaersuche:anleitung|Vollständige Erklärung und Anleitung]]

<code python 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
</code>

<nodisp 1>
++++Lösung|
<code python binaere_suche_loesung.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(l) - 1
    while links <= rechts:
        mitte = (links + rechts) // 2
        if li[mitte] == el:
            return mitte
        elif li[mitte] > el:
            rechts = mitte - 1
        else:
            links = mitte + 1
    return None
</code>
++++
</nodisp>
#### Aufgabe B4: Binäre Suche mit Postleitzahlen
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.

<nodisp 1>
++++Lösung|
<code python>
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))
</code>
++++
</nodisp>


#### Aufgabe B5: Zeitmessung mit linearer und binärer Suche
Vergleiche die lineare Suche mit der binären Suche. Hierzu kannst du von Aufgabe B4 ausgehen (unter neuem Namen speichern):
  - Behalte nur die Listen und die Definition der Funktion ''binary\_search()''.
  - Ergänze die Datei um die Funktion ''linear\_search(li, el)'' (am besten, du schreibst du sie selbst hin, anstatt sie zu kopieren).
  - 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."
  - Rufe nun die Funktion vier mal auf: Für die Postleitzahlen 1000 und 8590 – jeweils mit der linearen und mit der binären Suche.

<nodisp 1>
++++Lösung|
<code python>
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
</code>
++++
</nodisp>


#### Aufgabe B6: Nach Orten suchen.
Was passiert, wenn du statt nach Postleitzahlen nach Orten suchst? Funktioniert die Binärsuche? Weshalb nicht? Was müssten wir ändern, damit sie funktioniert?

<nodisp 1>
++++Lösung:|
Die Liste muss **sortiert** sein, damit wir Binärsuche verwenden können. Das Dataset ist aber nach PLZ sortiert, nicht nach Ortsnamen. Wir müssten ein Kopie anfertigen und alle drei Listen nach Ortsnamen sortieren.
++++
</nodisp>
#### Aufgabe B7: Mehrere Suchresultate (optional).
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:
<code python>
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
</code>

<nodisp 1>
++++Lösung|
<code python>
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
</code>
++++
</nodisp>


#### Aufgabe B8: Rekursion (optional)
Bei der binären Suche gehen wir ja wie folgt vor:
  - Index in der Mitte des Suchintervalls wählen.
  - Element in der Mitte auslesen.
  - Ist `element == suche` sind wir fertig.
  - Andernfalls wiederholen wir die Suche mit einem kleineren Teilintervall (zurück zu Schritt 1):
    - Ist `suche < element`, so ist das neue Suchintervall die linke Hälfte.
    - 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.

<nodisp 1>
++++Lösung|
<code python binaere_suche_rekursiv.py>
def binaere_suche_rekursiv(l, suche, links=None, rechts=None):
    """Gibt den Index des gesuchten Elements in l zurück,
       None, wenn das Element nicht existiert."""
    # Falls links und rechts nicht angegeben werden, sind sie None
    # Wir setzen sie so, dass sie die ganze Liste umfassen:
    links = links or 0
    rechts = rechts or len(l) - 1

    # Links ist grösser als rechts - nicht gefunden.
    if links > rechts:
        return None
    
    # 1: Intervall halbieren
    mitte = (links + rechts) // 2
    # 2: Element in der Mitte auslesen
    element = l[mitte]
    # 3: Element gefunden?
    if element == suche:
        return mitte
    # 4: Rekursion
    if suche < element:
        rechts = mitte - 1
    else:
        links = mitte + 1
    return binaere_suche_rekursiv(l, suche, links, rechts)
</code>
++++
</nodisp>


----
Weiter zu [[gf_informatik:suchen_und_sortieren:sortieren|Sortieren]]