| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung |
| 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-04-07 11:50] (aktuell) – [Aufgabe B3: Binäre Suche in Python] hof |
|---|
| |
| Weiter zu [[gf_informatik:suchen_und_sortieren:sortieren|Sortieren]] | 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. | <blockquote>Fast is better than slow. |
| |
| 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. | 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 | #### Aufgabe B2: Binäre Suche berechnen |
| |
| 1. 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? | 1. 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| | ++++Lösung| |
| |
| <nodisp 1> | <nodisp 1> |
| ++++Lösung| | ++++Lösung| |
| <code python binaere_suche_loesung.py> | <html><bottom-editor> |
| def binary_search(l, v): | def binary_search(l, v): |
| """Gibt den Index des gesuchten Elements in l zurück, None, | |
| wenn das Element nicht existiert.""" | |
| links = 0 | links = 0 |
| rechts = len(l) - 1 | rechts = len(l) - 1 |
| | |
| while links <= rechts: | while links <= rechts: |
| mitte = (links + rechts) // 2 | 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 | rechts = mitte - 1 |
| else: | else: |
| | # Rechts weitersuchen |
| links = mitte + 1 | 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> | </nodisp> |
| |
| |
| #### Aufgabe B4: Binäre Suche für 079 | #### 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: | 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)]]. | - Ö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: 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`). | - 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`). |
| - 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. | - 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. |
| - Dein Code sollte so aufgebaut sein, dass du nur die Variable `name` ändern musst, damit ein neuer, korrekter Satz ausgegeben wird. | - Dein Code sollte so aufgebaut sein, dass du nur die Variable `name` ändern musst, damit ein neuer, korrekter Satz ausgegeben wird. |
| |
| <nodisp 2> | <nodisp 1> |
| ++++Lösung| | ++++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 | from null79 import names, numbers |
| |
| telnr = numbers[index] | telnr = numbers[index] |
| print('Die Nummer von ' + name + ' lautet ' + telnr + '!') | print('Die Nummer von ' + name + ' lautet ' + telnr + '!') |
| </code> | </bottom-editor></html> |
| ++++ | ++++ |
| </nodisp> | </nodisp> |
| |
| |
| #### Aufgabe B5: Zeitmessung mit linearer und binärer Suche | #### Aufgabe B5: Zeitmessung mit linearer und binärer Suche |
| - Rufe nun die Funktion vier mal auf: Für `Annina` und `Lyanna` – jeweils mit der linearen und mit der binären Suche. | - Rufe nun die Funktion vier mal auf: Für `Annina` und `Lyanna` – jeweils mit der linearen und mit der binären Suche. |
| |
| <nodisp 2> | <nodisp 1> |
| ++++Lösung| | ++++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 | from null79 import names, numbers |
| import time | import time |
| telnr = numbers[index] | telnr = numbers[index] |
| elapsed = time.time() - start | 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') | stopwatch(linear_search, 'Annina') |
| stopwatch(linear_search, 'Lyanna') | stopwatch(linear_search, 'Lyanna') |
| stopwatch(binary_search, 'Lyanna') | stopwatch(binary_search, 'Lyanna') |
| </code> | </bottom-editor></html> |
| ++++ | ++++ |
| </nodisp> | </nodisp> |
| 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? | 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:| | ++++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. | 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. |
| </code> | </code> |
| |
| <nodisp 2> | <nodisp 1> |
| ++++Lösung| | ++++Lösung| |
| <code python> | <code python> |
| 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. | 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 2> | <nodisp 1> |
| ++++Lösung| | ++++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): | def binaere_suche_rekursiv(l, suche, links=None, rechts=None): |
| """Gibt den Index des gesuchten Elements in l zurück, | """Gibt den Index des gesuchten Elements in l zurück, |
| links = mitte + 1 | links = mitte + 1 |
| return binaere_suche_rekursiv(l, suche, links, rechts) | 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> | </nodisp> |
hof