Binäre Suche [KSR Wiki]

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
Zurück zu [[gf_informatik:suchen_und_sortieren#lineare_suche|Lineare Suche]]

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

==== Binäre Suche ====

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

=== Aufgabe B1: Suchen in einem Wörterbuch / Lexikon ===

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?

=== Algorithmus ===

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.

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

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 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(l) - 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 (`l[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>
++++

<nodisp 1>
[[gf_informatik:suchen_und_sortieren::binaersuche:anleitung|Vollständige Erklärung und Anleitung]]
</nodisp>

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

<nodisp 1>
++++Lösung|
<code python binaere_suche_loesung.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:
        mitte = (links + rechts) // 2
        if l[mitte] == v:
            return mitte
        elif l[mitte] > v:
            rechts = mitte - 1
        else:
            links = mitte + 1
    return None
</code>
++++
</nodisp>
#### Aufgabe B4: Binäre Suche für 079
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 [[https://webtigerpython.ethz.ch/?code=NobwRAdghgtgpmAXGGUCWEB0AHAnmAGjABMoAXKJMAMwCcB7GAAggFcAbdgdgE4m0Y2erTItYcAM4EWrGACM4tCQB0IqjMTgAPJgF4mAFgBMq6PD1j4E4Bu0BdVWTjsItC23mLrtrQ4jZaDDIACmUwABE0OCYAFWc4anoID3g3ADckpjCmAGpLaLzstAlRbLynF1oASjAAXwJwMwRkNk5eHHwiUgoqAGIAQgB6VglaQbkMQbwyAAsk1V6mAFoAKiWmAGN6YgwAc0QmVjJqAA5ltfVBYVEyAThpEsCIXelUWdVVDfYoCQkmAGVsFAlHAAApzCBwABC9HoAGtglVEKomKismAwmEAIJMCRAkFMdjFG4zchMWhwMisWgQP6zaIUtJeODEfiaCC3Mi4JiJNxQJi7NBMiD8CCaLTSAIJNBaFlMADuaHeIrRaP5UuoMswmIxGJVqM01CYAH1jRglabghJnNRJRTNVpdGEAAy8MJIlGqtHW9jUTDG9hwZ6zCwARmdEcjzs9XtxNv9GplFkTWg--qYhpNAaDlp91A96dVFKpNLjvv9geDMzTqszpt2lKVcBguZt0jQBdjqLQRq52DgwQ7_D-EHooiCyMLXdo6GtTAAkmLtABRWgMWihMCLtJQImsnwHMq4sgbjtVGNenv8JgAHiYzsnXcvuX0latNvPU-7Rudt_0aFvQkg3fX1OyfNFi2pEU8wTe0kzyXk3mCN88yqZYmFDdC0GkF0j0eQcOWCN4Zkwdh6F2cNkOA1Cqlo3J0TUMBPyfGdimiRdxVXddNw47QmHoI5-KNGdnjgQ8wHo_CzzTL4fj-QFgWtAAZYlEUfNEdWxXF8WtaRd2wUkFFuDZd3YbkJGuOUiRKJhZjJTQnFoGBzRKNATM4blIJpP4oAvNEmh5YQmDgKANhmAUhSDUVxWkbQNjgbBRF5Jh-WtDZiyYOE4FwQYd3YVhoiBNBaG1XVMXTOszQgC1jRA20gKrB44HSyljSy3AmpashjTygrpE0b5cF0Z0wNjGDjQGqBuX0SbcD87142zKsLErXZlSfca0uLNrsosLbWva-bUU25rtt66J9H27rzqOss_R6-h5WcP59AAcigOA0AE17bvGrZaSSKAORephgDCwK3HBjBjyeXZMB-DY0DQANHsUEy5yvcHR3HaDFoyJ72AkPwNsW4gBLkQMQdeuRiGoXZ2BgfwlDIH6vzu_1Ek4VGlD2yziDq_18eeyTSfJynPwvSrK1bUD1NjLzcfLJa1urdNJYSE1IS0br9MMyk6ukb4SlGr0jdEV8fjIUjucRW6rzN4AllDOxRXZh6CYkOXwIVt3_os6Bgbto03zNtC7yML2WMpKC3aFwmg8JS3HaMF3ob-pJ_aBshPduoto9Lca45UNmffGzmyKepQL3Vo1jQbSEZycY0mgN_gTdVTSIkpRRnOq1z3LMgUg0UchonpfIUpx8VrzoRhbJmaIoB3NBvgpxf2AMqAjKYBReWiK6et3ArSs0tQ2avADdEuxaD_ayPp3zxX7oPm7z6NAC7xOrqdtwe-xooEQFhoxs1VEGVk18la32yrnNUG89bmxhnseGEhEbI1YNgfstB0ZwGAA-R4SCEZI2NOgzB2DMA-AFsaF-R8cHOjsFUYm4FUTsBWsBXWW9KTMS7M9MSMDjoAIQV_ba7V6Khj4cFMUrCIB1S4Uw9h29LongISgohJC0Y_Bwfg54yDUHEIweo605ClxaEodQ_KtD6E5FDIgRhTCAJLAgc_U6B1dp5DEWfJ8ixARElEMAEowIyCIDAanDk9BCTBQAI6sF3EsCQaAABecogiKDyn8egRp-SrRDOklKcgBI40cnlQY7BbosNfGwuBHCyCyK9OApgxFMDxRXsEYIYD0L-JEGhQYhIamqh8BYIIg4mCDG6cQXp_lxAWHkZSGwxjbHPn_EwAApBmGsXZ5QzBXtEVkAA-DCf8vTTMEYtLWOtKlGWCE0cZsYykNWCEc65tSLANKaewYIrJunsEeX04xAzCIARGRmb5EzzA5H0Ec2Z4p5lPkvteFZxBbo-yaGsg0Gt6yNicC2WqeZ2ztzRLceAmAJCBgSpQ2ajyrx9gHEOYoLAxyikCeI1ic5eJaC4sIHiEA8poH3MY8SkkTyDlognD-94Dl9JfHc1CIq9COP9FA3-TLH5uzMQVRFyrxr1xHk3FuHY0weAUDzfQCkQTgiSNCWECIXRuiYqYcQIMTXKVUuGKMEZpAAGYeAAFZ3UnGMNIV6SlcBA2gK9GotQ7BAA&vanilla_python=true|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.

<nodisp 1>
++++Lösung|
<code python>
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 + '!')
</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(l, v)` (am besten, du schreibst du sie selbst hin, anstatt sie zu kopieren).
  - Definiere eine neue Funktion `stopwatch(algo, name)`. Sie hat zwei Argumente:
    - `algo` ist der Name der Suchfunktion (Suchalgorithmus), die verwendet werden soll (also `binary_search` oder `linear_search`, ohne die Klammern des Funktionsaufrufs).
    - `name` ist der Name, nach dem gesucht werden soll.
  - 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."
  - Rufe nun die Funktion vier mal auf: Für `Annina` und `Lyanna` – jeweils mit der linearen und mit der binären Suche.

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


#### Aufgabe B6: Nach Telefonnummern suchen.
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?

<nodisp 1>
++++Lösung:|
Die Liste muss **sortiert** sein, damit wir Binärsuche verwenden können. Das Telefonbuch ist aber nach Namen sortiert, nicht nach Telefonnummern. Wir müssten ein Kopie anfertigen und beide Listen nach Telefonnummer 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 funktioniert. 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]]