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-02-24 07:29] (aktuell) – [Aufgabe B4: Binäre Suche für 079] 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 36: / Zeile 35: @@
 . 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>
@@ Zeile 55: / Zeile 54: @@
 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 71: @@
 ++++
-<nodisp 2>
+<nodisp 1>
 [[gf_informatik:suchen_und_sortieren::binaersuche:anleitung|Vollständige Erklärung und Anleitung]]
 </nodisp>
@@ Zeile 101: / Zeile 99: @@
 </code>
-<nodisp 2>
+<nodisp 1>
 ++++Lösung|
 <code python binaere_suche_loesung.py>
@@ Zeile 121: / Zeile 119: @@
 ++++
 </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:
-  - Ö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`).
   - 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.