| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung |
| gf_informatik:suchen_und_sortieren:binaersuche [2025-10-24 09:32] – [Aufgabe B4: Binäre Suche für 079] gra | 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. |
| | <cite>[[https://about.google/company-info/philosophy/?hl=en#:~:text=3.%20Fast%20is%20better%20than%20slow.|Google]]</cite> |
| | </blockquote> |
| |
| ==== Binäre Suche ==== | ==== Binäre Suche ==== |
| 1. Wie sieht es mit einer Broschüre mit 15 oder 31 Seiten aus? Wie mit einem Buch mit 255 Seiten? | 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. 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? | 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| |
| |
| |
| 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. | 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 | #### Aufgabe B3: Binäre Suche in Python |
| |
| ++++ | ++++ |
| |
| <nodisp 2> | <nodisp 1> |
| [[gf_informatik:suchen_und_sortieren::binaersuche:anleitung|Vollständige Erklärung und Anleitung]] | [[gf_informatik:suchen_und_sortieren::binaersuche:anleitung|Vollständige Erklärung und Anleitung]] |
| </nodisp> | </nodisp> |
| </code> | </code> |
| |
| <nodisp 2> | <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/#?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)]]. | - Ö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> |
gra