Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung | ||
| gf_informatik:suchen_und_sortieren:binaersuche [2024-02-21 13:01] – hof | gf_informatik:suchen_und_sortieren:binaersuche [2026-02-24 07:29] (aktuell) – [Aufgabe B4: Binäre Suche für 079] hof | ||
|---|---|---|---|
| Zeile 2: | Zeile 2: | ||
| Weiter zu [[gf_informatik: | Weiter zu [[gf_informatik: | ||
| + | |||
| + | < | ||
| + | < | ||
| + | </ | ||
| ==== Binäre Suche ==== | ==== Binäre Suche ==== | ||
| Zeile 26: | Zeile 30: | ||
| Bei der Suche im Wörterbuch suchen wir zu Beginn nur die richtige Seite - wir teilen den Suchbereich, | Bei der Suche im Wörterbuch suchen wir zu Beginn nur die richtige Seite - wir teilen den Suchbereich, | ||
| - | |||
| #### Aufgabe B2: Binäre Suche berechnen | #### Aufgabe B2: Binäre Suche berechnen | ||
| Zeile 32: | Zeile 35: | ||
| 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, | + | 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, |
| - | < | + | < |
| ++++Lösung| | ++++Lösung| | ||
| Zeile 51: | 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, | 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, | ||
| - | |||
| #### Aufgabe B3: Binäre Suche in Python | #### Aufgabe B3: Binäre Suche in Python | ||
| Zeile 121: | Zeile 123: | ||
| Kannst du nun die Funktion für die binäre Suche selbständig, | Kannst du nun die Funktion für die binäre Suche selbständig, | ||
| - | - 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:// |
| - | - Importiere | + | - Alternative: |
| - Schreibe selbständig deine Funktion `binary_search(l, | - Schreibe selbständig deine Funktion `binary_search(l, | ||
| - Definiere unter einer Variable namens `name` den gesuchten Namen, also `Lyanna`. | - Definiere unter einer Variable namens `name` den gesuchten Namen, also `Lyanna`. | ||
| Zeile 130: | Zeile 132: | ||
| - 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. | ||
| - | < | + | < |
| ++++Lösung| | ++++Lösung| | ||
| <code python> | <code python> | ||
| Zeile 175: | Zeile 177: | ||
| - 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. | ||
| - | < | + | < |
| ++++Lösung| | ++++Lösung| | ||
| <code python> | <code python> | ||
| Zeile 224: | Zeile 226: | ||
| Was passiert, wenn du statt nach Telefonnummern statt nach Namen suchst? Funktioniert die Binärsuche? | Was passiert, wenn du statt nach Telefonnummern statt nach Namen suchst? Funktioniert die Binärsuche? | ||
| - | < | + | < |
| ++++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 249: | ||
| </ | </ | ||
| - | < | + | < |
| ++++Lösung| | ++++Lösung| | ||
| <code python> | <code python> | ||
| Zeile 287: | Zeile 289: | ||
| 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. | ||
| - | < | + | < |
| ++++Lösung| | ++++Lösung| | ||
| <code python binaere_suche_rekursiv.py> | <code python binaere_suche_rekursiv.py> | ||
hof