Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- gf_informatik:suchen_und_sortieren:binaersuche [2026-02-14 13:41] – hof
+++ gf_informatik:suchen_und_sortieren:binaersuche [2026-05-02 12:30] (aktuell) – [Aufgabe B8: Rekursion (optional)] hof
@@ Zeile 36: / Zeile 36: @@
 . Wie sieht es mit einer Broschüre mit 15 oder 31 Seiten aus? Wie mit einem Buch mit 255 Seiten?
 . Erkennst du einen (mathematischen) Zusammenhang zwischen der Anzahl Seiten und der Anzahl Aufschlagen?
-. 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?
+. 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?
-<nodisp 2>
+<nodisp 1>
 ++++Lösung|
@@ Zeile 55: / Zeile 55: @@
 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
@@ Zeile 73: / Zeile 72: @@
 ++++
-<nodisp 2>
+<nodisp 1>
 [[gf_informatik:suchen_und_sortieren::binaersuche:anleitung|Vollständige Erklärung und Anleitung]]
 </nodisp>
-<code python binaere_suche.py>
+<bottom-exercise id="b3" timeout="5" showsolution>
+<template data-type="starter">
 def binary_search(l, v):
     """Gibt den Index des gesuchten Elements in l zurück, None,
@@ Zeile 88: / Zeile 88: @@
     return None
-# TEST YOUR FUNCTION
+# Test
-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
+</template>
-print(binary_search(['A','C','D','G','J','N','Q','X'],'Q')) # output must be: 6
+<template data-type="solution">
-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 2>
-++++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:
+        element = l[mitte]
-            return mitte
+        print(f'Besuche {mitte} ({element}) im Intervall {links}-{rechts}')
-        elif l[mitte] > v:
+        if element == v:
+            return mitte  # Gefunden!
+        if v < element:
+            # Links weitersuchen
             rechts = mitte - 1
         else:
+            # Rechts weitersuchen
             links = mitte + 1
-    return None
-</code>
+    return None  # Nichts gefunden
-++++
-</nodisp>
+print(binary_search(['A','C','D','G','J','N','Q','X'],'J')) # output must be: 4
+</template>
+<template data-type="test">
+assert binary_search(['A','C','D','G','J','N','Q','X'],'B') is None
+assert binary_search(['A','C','D','G','J','N','Q','X'],'A') == 0
+assert binary_search(['A','C','D','G','J','N','Q','X'],'C') == 1
+assert binary_search(['A','C','D','G','J','N','Q','X'],'D') == 2
+assert binary_search(['A','C','D','G','J','N','Q','X'],'G') == 3
+assert binary_search(['A','C','D','G','J','N','Q','X'],'J') == 4
+assert binary_search(['A','C','D','G','J','N','Q','X'],'N') == 5
+assert binary_search(['A','C','D','G','J','N','Q','X'],'Q') == 6
+assert binary_search(['A','C','D','G','J','N','Q','X'],'X') == 7
+assert binary_search(['A','C','D','G','J','N','Q','X'],'Z') is None
+</template>
+</bottom-exercise>
 #### 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:
-  - Öffne [[https://wtp.ethz.ch/#?layout=%5B%22Editor%22%2C%20%22Console%22%5D&code=NobwRAdghgtgpmAXGANgezQBwHSYJ5gA0YAJlAC5RJgCMADAEyE00AszLzdAnIQMxMW7FgHYOdcVxod2ArgFYuvFoM5COANn6C6Y-ovoAOLse6LueusaOEzm23poHdHRXPpdLz61dvnLPqYGNFoWrp7hrBKsNGAAvoTg0PDUMFAAlhC4BMRklNQAZgBOaDAABBAArigoItxl6TCYaEXkFbBwAM6EFZUwAEZwRZ0AOhBlY5kkcAAeZQC8ZawMY8lwC-3wncBTswC6Y-RwKBBFG1UDQ9u7MwcQmEWZ5AAUI2AAIunrACrHcAVoCAXeBnABugImYDKAGpNutYW8Gp02ojYUcTkUAJTxRKQDrUKo1OrZIikChUZAAYgAhAB6SqdIq0_qZWn4cgAC0BY0pZQAtAAqPllADGaBImQA5ogypVyAVDPyhZMmi02uRGnAesjHhBJT00pyxmMRSgoJ1OmUAMqYKDDOAABS5EDgACEMABrZ6YxBjMr-yFvN4AQTKnVt9rKKHSyLKnIoZSKcHIlSKEEtnPWSdBVzgJAa0wgGvIeDKALOUDKkvSOfGNx6D3-6RmebKAHd0kbxgGA5XGwVm9gg2Ag93_dMCmUAPpTzKdmfPTrHAoNpMDmbzN66bhvH1-nsBpcoArYKcoOB6zkbeh0W93_cHsPL0_95sbV8zY1jsoT6dni8LkeBR7t-PZJimaZPsep7npeHJfj2v4zpKyadnAMCAcuPTpCBj7-ukk4lpgcDPDhSIVGgbRPL6oF4UUGRLmUACSEDTDMACiRQlEUrxgCxoJQNG-Y3DKqJhuQPE4ZiD4HgRDRlAAPGUdA0XhskwossGLsu0m0fhk50IpizpIpUYXtpx64WpAbgam4xAS-a5vrC5aGs8WlAZi_JlDQ3npD0W5iTqpFFs8hoctg6CSvQ7nmZ5mIJTCkIQLuMlgQx6wsWxnHcbxWWzGUaByoVk70XqcCiVCsLBVJX6mualo2naS4ADIxi8Vn-sOIZhhGS49IJmAclAgwaiKgkoKWnRqq20axvGbTTEcRQwHOyLpONNSlrZaaWlAaX-msZYtGUcBQCKHJVjWF4NKxsw9LMIpwJgbTlmUlZLiK4FlB6cB4LSAkoJU6y2ukRRDiOkMyUhs4QPOU4WSuZlwdqcBfcmU6_XgqPo-QU6A8DPTTGaeDzHQnUHg5U7E1ApaLDTeAHf6VOwZKV6aRebPwXpUEnlOn3gZjf0bALGNY0zvOnqLeME-sizS_jgnAxLVPgm2xyWosADkUBwOkRVayrz5TmK6aAlARaa2UwAXcdZy25k4m6pK2DmiK6TpGeaDq0U42MXJtsQJRt2S_j3sa3calUyQRX9OeVta_0JAFJKKAwPcwzkIbPNUwCNTh8MIszSQiOnmrGtJdHsfx7p0P_H-sGYZZql0cmdmh6zXY9nXk5Ti6Mx44Nw2jYjPRmsiFM9uPbSaea5CRQX3oS3J0_AHyNB7CHqvhygnQt9ZiZt5BVOm9N0CW8vk5adPXlKQw-_WTt9nG-Xu-X1Gc9rwwm-OyfgJnxbcge8JZgSPs_aCYd1Zvx5k_UOed0A-1GN-Hu04UIunokcPuHRR4NEngGbqHxkxDFWnDdam1JpVgvEMCg6xMxwnelRO6cwTLFFKHGDk6woACXSGaOOnCUBDRGsmMogxyzrAVrLCG3UUo8zkiZeY8tjYKyxg_NSsCqYSKVnAd-JklIaLRoLFRIDDyUFaBsOgxj_QXnzIoiByi_qWPegI4ewj5YSSlK7To7tPaVEwMRX25o4DABUjqDxbsPZTl8f4v2cBsA3FLvzAxGNZbBL2JiSOB8owbC0kPIR5BdJqQ1hVRxyI7Qz1DvY0ssIaCOOsdkuKOlHG5NGiLdxepPHeMiX4oYMTgChPaeEnx3SAlLjiUwhJmigZBLoGk6ENBEAZIPiZPkti-aVKSjUmRaleQ2mjG0PppjyCIGsT_IsaAslwAAI6VEEnyTo6QABerYnhDEBpaNAk5Kyd0uh896_QiqMOWoDWkKAJYoHqRAZ4zTkwFLwjYso4VsBPR4c8Z4dThSlNaF5WkUZYWPhuBsJ4pEyi0hxSQPFB4jqLGheQHYTDFnqWMmUAApD-BCeE2wch4esfMAA-Hyqi8I0pFsbfug9nF5OeGsClalwUc0hTSmVcKNiIuRSgZ4-YcUoCVfiphhLQomVJT-HVlKOgaScYI0adK2IMrUvI-SrKSAS1gWsdl4567IVQkcDCCMgLYTwf6DU8BsCdHPM9BJDMTVySIiRMiMYKKAsFY-eiMZMpMJyi0PKEBAbpGEkwyqlcJKkQSjo0yKlHEmWhPKxGUbJzyNWVLJJeMjE81ARBcBaym2Kymc6sBoc0HUMwWsYtX4LiDELosJq9onSAjdJ6Xi25UpAg6FbKdrV2rPBvHeW8PQ-BmD4IYZYPQtYtTwBbaAWtsRxD2EAA|WebtigerPython mit der bereits hinterlegten Telefonbuch-Datei (null79.py)]].
+<bottom-exercise id="b4" timeout="5" zip="https://bottom.ch/ksr/1m/null79.py.zip" showsolution>
-    - Alternative: Erstelle eine neue, leere Python-Datei und speichere sie (Name z.B.: `aufgabe_b4.py`) im gleichen Ordner wie die Datei `null79.py`. Importiere das Modul `null79`, das du schon in Aufgabe A3 verwendet hast (`from null79 import names, numbers`).
+<div slot="prompt">
-  - 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.
+Kannst du nun die Funktion für die binäre Suche selbständig, also <em>ohne nachzuschauen</em>, schreiben und diese auch verwenden, um in Listen zu suchen? Versuche es:
-  - 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 2>
+<ul>
-++++Lösung|
+  <li>Schreibe selbständig deine Funktion <code>binary_search(l, v)</code>: Sie soll die Position von <code>v</code> in der Liste <code>l</code> zurückgeben. Wenn nichts gefunden wird, soll die Funktion <code>None</code> zurückgeben.
-<code python>
+  <li>Definiere unter einer Variable namens <code>name</code> den gesuchten Namen, also <code>Lyanna</code>.
+  <li>Jetzt suchst du mit <code>index = binary_search(names, name)</code> nach dem Index von <code>name</code> in der Liste <code>names</code>.
+  <li>Unter dem gleichen Index findest du in <code>numbers</code> die dazugehörige Telefonnummer.
+  <li>Gib einen Satz im Format <code>Die Telefonnummer von ... ist ...</code> aus.
+  <li>Dein Code sollte so aufgebaut sein, dass du nur die Variable <code>name</code> ändern musst, damit ein neuer, korrekter Satz ausgegeben wird.
+</ul>
+</div>
+<template data-type="starter">
+from null79 import names, numbers
+def binary_search(l, v):
+    """Gibt den Index des gesuchten Elements in l zurück, None,
+       wenn das Element nicht existiert."""
+</template>
+<template data-type="solution">
 from null79 import names, numbers
@@ Zeile 163: / Zeile 177: @@
     telnr = numbers[index]
     print('Die Nummer von ' + name + ' lautet ' + telnr + '!')
-</code>
+</template>
-++++
+<template data-type="test">
-</nodisp>
+assert binary_search(['A','C','D','G','J','N','Q','X'],'D') == 2
+assert binary_search(['A','C','D','G','J','N','Q','X'],'Z') is None
+assert binary_search(names,'Lyanna') >= 0
+</template>
+</bottom-exercise>
 #### 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 2>
+<bottom-exercise id="b5" timeout="120" zip="https://bottom.ch/ksr/1m/null79.py.zip" showsolution>
-++++Lösung|
+<div slot="prompt">
-<code python>
+Vergleiche die lineare Suche mit der binären Suche. Hierzu kannst du von Aufgabe B4 ausgehen:
+<ul>
+  <li>Behalte nur die Listen und die Definition der Funktion <code>binary_search()</code>.
+  <li>Ergänze die Datei um die Funktion <code>linear_search(l, v)</code> (am besten, du schreibst du sie selbst hin, anstatt sie zu kopieren).
+  <li>Definiere eine neue Funktion <code>stopwatch(algo, name)</code>. Sie hat zwei Argumente:
+  <ul>
+    <li><code>algo</code> ist der Name der Suchfunktion (Suchalgorithmus), die verwendet werden soll (also <code>binary_search</code> oder <code>linear_search</code>, ohne die Klammern des Funktionsaufrufs).
+    <li><code>name</code> ist der Name, nach dem gesucht werden soll.
+    </ul>
+  <li>Die Funktion soll mit dem gewünschten Algorithmus im Telefonbuch suchen und die Zeit für die Suche messen (<code>import time</code>, siehe auch Aufgabe A5). Am Ende soll die Funktion einen Text in folgender Form ausgeben: "Die Telefonnummer von ... lautet .... Die Suche dauerte ... Sekunden."
+  <li>Rufe nun die Funktion vier mal auf: Für <code>Annina</code> und <code>Lyanna</code> – jeweils mit der linearen und mit der binären Suche.
+</ul>
+</div>
+<template data-type="starter">
+from null79 import names, numbers
+def binary_search(l, v):
+    """Gibt den Index des gesuchten Elements in l zurück, None,
+       wenn das Element nicht existiert."""
+    # TODO implementieren
+def linear_search(l, v):
+    """Gibt den Index des gesuchten Elements in l zurück, None,
+       wenn das Element nicht existiert."""
+    # TODO implementieren
+def stopwatch(algo, name):
+    """Ruft die Funktion algo auf und misst die Zeit der Ausführung."""
+stopwatch(binary_search, 'Annina')
+</template>
+<template data-type="solution">
 from null79 import names, numbers
 import time
@@ Zeile 213: / Zeile 253: @@
     telnr = numbers[index]
     elapsed = time.time() - start
-    print('Die Nummer von {0} lautet {1}! Die Suche dauerte {2:.2f}s.'.format(name, telnr, elapsed))
+    print(f'Die Nummer von {name} lautet {telnr}! Die Suche dauerte {elapsed:.2n}s.')
 stopwatch(linear_search, 'Annina')
@@ Zeile 219: / Zeile 259: @@
 stopwatch(linear_search, 'Lyanna')
 stopwatch(binary_search, 'Lyanna')
-</code>
+</template>
-++++
+</bottom-exercise>
-</nodisp>
@@ Zeile 227: / Zeile 267: @@
 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 2>
+<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.
@@ Zeile 250: / Zeile 290: @@
 </code>
-<nodisp 2>
+<nodisp 1>
 ++++Lösung|
 <code python>
@@ Zeile 275: / Zeile 315: @@
 ++++
 </nodisp>
 #### Aufgabe B8: Rekursion (optional)
+<bottom-exercise id="b8" timeout="5" zip="https://bottom.ch/ksr/1m/null79.py.zip" showsolution>
+<div slot="prompt">
 Bei der binären Suche gehen wir ja wie folgt vor:
-  - Index in der Mitte des Suchintervalls wählen.
+<ul>
-  - Element in der Mitte auslesen.
+  <li>Index in der Mitte des Suchintervalls wählen.
-  - Ist `element == suche` sind wir fertig.
+  <li>Element in der Mitte auslesen.
-  - Andernfalls wiederholen wir die Suche mit einem kleineren Teilintervall (zurück zu Schritt 1):
+  <li>Ist <code>element == suche</code> sind wir fertig.
-    - Ist `suche < element`, so ist das neue Suchintervall die linke Hälfte.
+  <li>Andernfalls wiederholen wir die Suche mit einem kleineren Teilintervall (zurück zu Schritt 1):
-    - Andernfalls ist `element < suche`, das neue Suchintervall ist die rechte Hälfte.
+    <ul>
+      <li>Ist <code>suche &lt; element</code>, so ist das neue Suchintervall die linke Hälfte.
+      <li>Andernfalls ist <code>element &lt; suche</code>, das neue Suchintervall ist die rechte Hälfte.
+    </ul>
+</ul>
-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`?
+<p>Schreibe eine neue Funktion, <code>binaere_suche_rekursiv(l, suche, links, rechts)</code>. Die Funktion codiert die obigen Schritte &ndash; statt einer <code>while</code>-Schleife soll die Funktion sich im Schritt 4 selber wieder aufrufen. Dieses Verfahren heisst <strong>Rekursion</strong>. Was sind die Startparameter für <code>links</code> und <code>rechts</code>?
-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.
+<p>Rekursion eignet sich für viele Probleme, die sich mit <em>Divide &amp; Conquer</em> (<em>Teile &amp; Herrsche</em>) 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.
+</div>
+<template data-type="starter">
+from null79 import names, numbers
+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."""
+</template>
+<template data-type="test">
+assert binaere_suche_rekursiv(names, 'Lyanna', links=0, rechts=len(names)) >= 0
+assert binaere_suche_rekursiv(names, 'Lyanna') >= 0, "Aufruf ohne links / rechts sollte auch funktionieren"
+</template>
+<template data-type="solution">
+from null79 import names, numbers
-<nodisp 2>
-++++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,
@@ Zeile 318: / Zeile 375: @@
         links = mitte + 1
     return binaere_suche_rekursiv(l, suche, links, rechts)
-</code>
-++++
+from null79 import names, numbers
-</nodisp>
+print(f'Die Telefonummer von Lyanna ist {numbers[binaere_suche_rekursiv(names, "Lyanna")]}.')
+</template>
+</bottom-exercise>