Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- gf_informatik:suchen_und_sortieren:binaersuche [2025-02-24 20:05] – hof
+++ gf_informatik:suchen_und_sortieren:binaersuche [2026-04-07 11:50] (aktuell) – [Aufgabe B3: Binäre Suche in Python] hof
@@ Zeile 2: / Zeile 2: @@
 Weiter zu [[gf_informatik:suchen_und_sortieren:sortieren|Sortieren]]
+<html><script type="module" src="https://bottom.ch/editor/stable/bottom-editor.js"></script></html>
+<blockquote>Fast is better than slow.
+<cite>[[https://about.google/company-info/philosophy/?hl=en#:~:text=3.%20Fast%20is%20better%20than%20slow.|Google]]</cite>
+</blockquote>
 ==== Binäre Suche ====
@@ Zeile 32: / Zeile 38: @@
 . 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 1>
@@ Zeile 51: / Zeile 57: @@
 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 99: / Zeile 104: @@
 <nodisp 1>
 ++++Lösung|
-<code python binaere_suche_loesung.py>
+<html><bottom-editor>
 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
+print(binary_search(['A','C','D','G','J','N','Q','X'],'J')) # output must be: 4
+</bottom-editor></html>
 ++++
 </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`.
+  - Öffne [[https://wtp.ethz.ch/#?code=NobwRAdghgtgpmAXGANgezQBwHSYJ5gA0YAJlAC5RJgCMADAEyE00AszLzdAnIQMxMW7FgHYOdcVxod2ArgFYuvFoM5COANn6C6Y-ovoAOLse6LueusaOEzm23poHdHRXPpdLz61dvnLPqYGNFoWrp7hrBKsNGAAvoTg0PDUMFAAlhC4BMRklNQAZgBOaDAABBAArigoItxl6TCYaEXkFbBwAM6EFZUwAEZwRZ0AOhBlY5kkcAAeZQC8ZawMZWUAxGUAKgDyACLbiGUAypUAxgAWcGXT4wCSENNzAG5o4wAyeFAQ0ACEY8lXRYAzrAKazAC6Y3IcBQECKC16AyGILBM0hEEwRUy5AAFAUAOS7dJXTYwuAFV5VGDweEvcYgAFxBqdNogaGwopxfEASniiUgHWoVRqdWyRFIFCoyDWPwA9JVOkVZf1MrL8ORzq8xhsALQAKh1ZVOaBImQA5odKuQCoYyvqdZMmi02uRGnAeiysRAzT00hqxmNTigoJ1OsdMFBhnAAAqaiBwABCGAA1jjuYgxqtViMwDmcwBBMqdCNRsoodIssoaihlIpwciVIoQMMaq51p7IuAkBo3V3kPBlCnwqBlM3pDvjVE9THk9IzLtlADu6X94yzWZHM4Kc-wedzubXq2mBTKAH1T5kV-ecZ0YQVp3XtzN5jndNwc-nM-us7eUAVsKeKBwN6GoIvQdAQZBX7fkWd4AVuc4IghMwBoe1zkmegHAdev4FJ-aHrnWDZNrBf4AUBIHnKh67HphZr1iucAwDhd49Ok-Ewas6Qnv2mBwDi7HMhUaBtNiGYEZxRQZLeZT3I8ACiRQlEUOI5vcTxQOW3aoocOZlAA1EW5Aqex3LQd-3ENGUAA8ZR0OJnEWQZiwUTed5mRJXEnnQNmLOkNllsBbl_hxjlZkRjbjLh8GPohhlDn6OKubh3J2mUNBpekPSvnphmegJEC4n65zYOgZr0ElQUpdyNUGRMkAfuZhHSVccmzIpymqWAbVzGgVplGgJ5Sd6cC6WAdX5aZqFBiGYZHCWt5vBWuKhdm-4FkWC3umUmmYOcUCDK6pyaSgA6dM6C7lpW1ZtNM0JFDAl4sukx01AOEVNmGUBNasAKDi0ZRwFAFyjuOwENA8sw9LMpxwJgbRDjtsGnERZTJnAeCyhpKCVFcEbpEUu7rQeNEYeel7kCxf49BRZoah6cAo_Wp7o3gDNM5T2O4z00zBng8x0Kt37RaevNQAOixi3gP2rCLtOgS5wF01Rnmkf-p63hzLMYwimtEdr0uqyLevM1zgLI_rZsy2rAEvIuMJhos-JQHA6R9fi1si8azavF85CO2UwAg4jIOZEZXpmtgIanOk6SAWg9tFMdMmWSDEAiRDNunnbDvoo5IskH1_RAQH-L9CQBRmigMAYsM5Ae0bcGnhSNQJ8iusXSQwXqznKBhnlTeF5UxddB55m0eeFFU3hDmSfWkVZ_LKvruPZPxjMlO7fth3dzTIbkEL67BpWLn76VbcqR5jmWcf5DADqNDgpnIu950s9hbW88kV7rzndAhWjFVjfIKt9Uq2QYO_MKH0opN1ftbG--974MCfmHH-Pt_7-0gY5aBWc4GqxwSLFu6BE6AJXmhCe9F4xSWhKeAEu8GiHyzHuHMux6xDEehAZaL0ToDkoUMCgVxWztHgDtUSkM5j-WKKUKslwdoaXSMGEeO0UB7QOvWMogwhxXBNpzTSuMibMIgPAk8_l5iLGNozfWrMsFz2IjAsiGtLGmz0XAYxVlbIWK1tY6264WSRjaIsOgPiszAW7OYpuOiDbBNWFvNRATw7mijp0GOcdKiYD4knEMcBgD2U9Ik6OsdTxpIycnOA2BUTdwApEs2OTwTcjzh_MsCJXKxMOlfTiDtRrRKMv43WESnGU1ZnVGg3TQnNKqu5bprT1HmOMvk5JhTilDFKcAPJ3okkpKKek5ZWTyniMqY4rWNS6B1P0jQRADSP7-R1OEhxkShmGRGUY1WGx5rljaKsygrREChJQYVNATS4AAEdKiaR1J0dIAAvBc2IhjYzDINJGS8BongOn1MR91sayhQNbFA4yIA4mmQfa2YSyjFWwLDBROIcRjMNH41oqVZRlnaTBVECJsQCTKLKJlJAWXfj-osIloJxGXKcn5MoABSa41FOKLnOAoq43YAB86UbEwSJX0hx69N4qO3vWHEAI-WOTxYrAlRKjWcVJeSylKAcTdiZSgC1rLxHssKpy7l1wnX8o6M5ZRqjDrCseKK6-7LJXSvwV_cYAIZVHjJqeeifYmLTzYow1Yrp4DYE6EBOGBypZessrxfigkKzCQxWq78UkKytXER1FoXV1KaXSNpcRY0JrGQEjVNx_lbL2W6f5fSpru75pMQsW56t7kY3LYRSNWdqkuOtgQpufDqFwFoR0DtqEqSDGGAieakZbyxleImFMXU3yNW-B0AOe6oxLRZDicCkEII9D4GYPghhlg9HxB8L40AeTxHBEAA|WebTigerPython mit der bereits hinterlegten Telefonbuch-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]].
+    - 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`).
-  - 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`.
@@ Zeile 132: / Zeile 143: @@
 <nodisp 1>
 ++++Lösung|
-<code python>
+<html><bottom-editor timeout="180" zip="https://sca.ksr.ch/lib/exe/fetch.php?media=gf_informatik:programmieren_i:null79.py.zip">
 from null79 import names, numbers
@@ Zeile 160: / Zeile 171: @@
     telnr = numbers[index]
     print('Die Nummer von ' + name + ' lautet ' + telnr + '!')
-</code>
+</bottom-editor></html>
 ++++
 </nodisp>
 #### Aufgabe B5: Zeitmessung mit linearer und binärer Suche
@@ Zeile 177: / Zeile 187: @@
 <nodisp 1>
 ++++Lösung|
-<code python>
+<html><bottom-editor timeout="180" zip="https://sca.ksr.ch/lib/exe/fetch.php?media=gf_informatik:programmieren_i:null79.py.zip">
 from null79 import names, numbers
 import time
@@ Zeile 210: / Zeile 220: @@
     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 216: / Zeile 226: @@
 stopwatch(linear_search, 'Lyanna')
 stopwatch(binary_search, 'Lyanna')
-</code>
+</bottom-editor></html>
 ++++
 </nodisp>
@@ Zeile 289: / Zeile 299: @@
 <nodisp 1>
 ++++Lösung|
-<code python binaere_suche_rekursiv.py>
+<html><bottom-editor timeout="180" zip="https://sca.ksr.ch/lib/exe/fetch.php?media=gf_informatik:programmieren_i:null79.py.zip">
 def binaere_suche_rekursiv(l, suche, links=None, rechts=None):
     """Gibt den Index des gesuchten Elements in l zurück,
@@ Zeile 315: / Zeile 325: @@
         links = mitte + 1
     return binaere_suche_rekursiv(l, suche, links, rechts)
-</code>
+from null79 import names, numbers
+print(f'Die Telefonummer von Lyanna ist {numbers[binaere_suche_rekursiv(names, "Lyanna")]}.')
+</bottom-editor></html>
 ++++
 </nodisp>