Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- gf_informatik:suchen_und_sortieren:binaersuche [2026-02-24 07:29] – [Aufgabe B4: Binäre Suche für 079] hof
+++ gf_informatik:suchen_und_sortieren:binaersuche [2026-05-02 12:30] (aktuell) – [Aufgabe B8: Rekursion (optional)] hof
@@ Zeile 30: / Zeile 30: @@
 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
@@ Zeile 37: / Zeile 38: @@
 . 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 75: / Zeile 76: @@
 </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 86: / 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 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:
+        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/#?code=NobwRAdghgtgpmAXGANgezQBwHSYJ5gA0YAJlAC5RJgCMADAEyE00AszLzdAnIQMxMW7FgHYOdcVxod2ArgFYuvFoM5COANn6C6Y-ovoAOLse6LueusaOEzm23poHdHRXPpdLz61dvnLPqYGNFoWrp7hrBKsNGAAvoTg0PDUMFAAlhC4BMRklNQAZgBOaDAABBAArigoItxl6TCYaEXkFbBwAM6EFZUwAEZwRZ0AOhBlY5kkcAAeZQC8ZawMZWUAxGUAKgDyACLbiGUAYlNwZdPjRekAxgAW5OkA5nDjAJIQ03MAbmjjADJ4KAQaAAQjGyTOiwhnWApxmAF0xuQ4CgIEUFr0BkMYXDERBMFcIOQABQFADku3SZ02KLgBV-VRg8HRP3GIAhcQanTaIGRqKKcTJAEp4olIB1qFUanVskRSBQqMg1iCAPSVTpFFX9TIq_DkW6_MYbAC0ACpjWVrmgSJlHodKuQCoYymbjZMmi02g94D1uYTHj00vqxmNrigoJ1OmUAMqYKDDOAABQNEDgACEMABrYlCxBjVarEZgItFgCCZU6cYTZRQ6W5ZX1FDKRTg5EqRQgUf1ZxbX2xcBIDQuD3IeDK9PRUDKj3SffGcJ6BLp6RmA7KAHd0sHxgWC1OlwUV9gS8XizvVtMCmUAPrXzJb2_EzoogqLluHmbzIu6bhF3P53cC2fFACmwa8UBeR59Qxeg6Dg-CAMAisXzAg8VwxNCZhDc9zjpG9wJeR9gIKf8cN3Fs2w7ZCQLAiCICg25sN3S98OeEc4BgIiXx6dJSKQ1Z0ivUdMDgYleK5Co0DaTJyDzMj-KKDJnzKd5PgAUSKEoimJIt3i-KBa0HOFDiLMoAGoK3IbTeKFRDAMEhoygAHjKOg5P4-zzMWOinxfWz5IEq86GcxZ0mcmsXl8kC-I8gsKPbcZiNQ990Isicg2JHziKFF0yhoXL0h6b9TIsv0xKJYkg1ubB0EeehMsi7KhWa8yJkgP87PIpSzlU2YNK0nSwF6uY0AdMo0CvRT6LgEywFasqbOwsMIyjWN42fP46xJGLC1PMsKyrZ8egMzBbigQYHmuAyUDHTpPTXWt60bNppmRIoYHvbkbmusd4o7KMoE61YIXHFoyjgKA7mnWcXgaD5Zh6WZrjgTA2gnMop2fa4KLKTM4DwFV9JQSozjjdIimPPaz2YvDb3vcguJAno6IY304Gx1trzxvA2Y5hmiZJnppnDPB5joHbAKS69hagMdFhlvAgdWKWWeg7zIO3DypaxiiufxjEdc57mleo0Dr0N_mDJJg32d1gW4BNqWfnXFEo0WMkoDgdJRrJR2UOvK1O1-IFyDdspgCh9GocySz_WwCNrnSdJwLQF2iiu5SHKhiApLh02wOd128S1_2SFG_oILDsl-hIApHhQGB8WGchfYC_Pr3pGpU-xA37pIKKzcLlAo1K0vy8r_y7JY286MZkj3IU1sEvb1XGJwqfadTGYGZOs6LoH5mI3ICXd3DetvKPmru-0_yPIcs_yGAY0aHhPOne74eF9i5sl6oqXA7utAIkow2730ig_HKLkGBf1in9RK_sh4gLvleB-T8GCvxjv_X4gCQ6dBgR5OB7dEEm0IVLTu6A05IILBvK815nipkUsia8EID4NBPtQqmuxWxDA-hALa30ahjnoUMCgZxuztHgBjaS8M5hhWKKUBstwzhQH0ukcMFdlEoFOudVsZRBgTjOBba89tKYniYvxByYV5iLG1rbI2-N8GL0ovAmi5s7GW2Jg7UBV4wouVsXzPWeBHFIW5PGNoiw6Am13C8QcNj_ZGONm3Xcu8dHhNjraeOnRE7J0qJgES6cIxwGAG5P0GSE5J2vLk_JGc4DYDhAPMCRj7bFPhEKYu38awYh8iki6t9-KuxmlEoClBWg21cQk_WFkaBDNWDErpjU_IzIxloveuibFWTKVkipVShg1OAKU-imTsmVLybswpdSZENLcQE5pdBWlmRoIgdp38wrGjieM9xgTWrTIgCbDYsZaxtH2SM2SMSMFEjQJ0uAABHSoBljSdHSAALzXDJIYRMowTQxhFei0EsXnVGtIt6RMVQoBNigeZEBiQ9NbH0pCsSyhVWwMjNRxJiRzItKE1oOUVQ1jpfZGRGIZJiTKCqXlJB-W7hBosGlj9cQmysY5AApOccxSF1y3DUWcQcAA-PKwTAKyrGWbLeO8VmpOJBCSV_EKXqypbK619KMRMpZSgYkg5eUoEdQKz4QqKphTFecb1UqOheWWdoi6sIZHPNioqsKKqSAkN_uMCEarcK0Loa2LcHE548XYasb0tTOgQRRlchW3qHLCVEuJOskkiUGq6nWHqMj-otEGnpAy6QjIyNmvNKyYlmoKp8eFNySywpmTtQPCtw7rHtwmUEpZpD4mfPtkm5x7dhGMLgMwjoA7sKMkGMMDEa0EzJl-OmLMg0fwdWBB0MOJ6NpbWJLBeCcEeh8DMHwQwywehkgBECaAwp4jwiAA|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>