Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
gf_informatik:suchen_und_sortieren:binaersuche [2024-02-04 08:44] – hofgf_informatik:suchen_und_sortieren:binaersuche [2025-02-24 20:05] (aktuell) – hof
Zeile 34: Zeile 34:
   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. Wie viele Seiten musst du maximal aufschlagen, um eine beliebige Person zu finden?
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung| ++++Lösung|
  
Zeile 50: Zeile 50:
 Binäre Suche ist also ein äusserst leistungsfähiger Algorithmus, um in einer sortierten Liste ein gewünschtes Element zu finden. Der Suchaufwand wächst nur [[https://www.equestionanswers.com/c/images/log2n.gif|logarithmisch]]: Verdoppelt sich die Seitenzahl, so wächst der Aufwand nur um //eine// Halbierung; bei der linearen Suche würde sich der Aufwand auch verdoppeln. Binäre Suche ist also ein äusserst leistungsfähiger Algorithmus, um in einer sortierten Liste ein gewünschtes Element zu finden. Der Suchaufwand wächst nur [[https://www.equestionanswers.com/c/images/log2n.gif|logarithmisch]]: Verdoppelt sich die Seitenzahl, so wächst der Aufwand nur um //eine// Halbierung; bei der linearen Suche würde sich der Aufwand auch verdoppeln.
  
-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
  
Zeile 69: Zeile 69:
 ++++ ++++
  
-<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>
Zeile 97: Zeile 97:
 </code> </code>
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung| ++++Lösung|
 <code python binaere_suche_loesung.py> <code python binaere_suche_loesung.py>
Zeile 117: Zeile 117:
 ++++ ++++
 </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:
  
   - Erstelle eine neue, leere Python-Datei und speichere sie (Name z.B.: `aufgabe_b4.py`) im gleichen Ordner wie die Datei `null79.py`.   - Erstelle eine neue, leere Python-Datei und speichere sie (Name z.B.: `aufgabe_b4.py`) im gleichen Ordner wie die 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]].
   - Importiere die das Modul `null79`, die 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.   - 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`.   - Definiere unter einer Variable namens `name` den gesuchten Namen, also `Lyanna`.
-  - Jetzt suchst du mit deiner Funktion `binary_search()` nach dem Index von `name` in der Liste `names`.+  - 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.   - Unter dem gleichen Index findest du in `numbers` die dazugehörige Telefonnummer.
   - Gib einen Satz im Format `Die Telefonnummer von ... ist ...` aus.   - 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.   - 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> <code python>
Zeile 175: Zeile 175:
   - 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> <code python>
Zeile 224: Zeile 224:
 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.
Zeile 247: Zeile 247:
 </code> </code>
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung| ++++Lösung|
 <code python> <code python>
Zeile 287: Zeile 287:
 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> <code python binaere_suche_rekursiv.py>
  • gf_informatik/suchen_und_sortieren/binaersuche.1707036286.txt.gz
  • Zuletzt geändert: 2024-02-04 08:44
  • von hof