Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung | |||
| gf_informatik:suchen_und_sortieren:binaersuche [2025-01-10 12:21] – hof | gf_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, | 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, | ||
| - | < | + | < |
| ++++Lösung| | ++++Lösung| | ||
| Zeile 69: | Zeile 69: | ||
| ++++ | ++++ | ||
| - | < | + | < |
| [[gf_informatik: | [[gf_informatik: | ||
| </ | </ | ||
| Zeile 97: | Zeile 97: | ||
| </ | </ | ||
| - | < | + | < |
| ++++Lösung| | ++++Lösung| | ||
| <code python binaere_suche_loesung.py> | <code python binaere_suche_loesung.py> | ||
| Zeile 130: | Zeile 130: | ||
| - 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 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. | ||
| - | < | + | < |
| ++++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? | 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 247: | ||
| </ | </ | ||
| - | < | + | < |
| ++++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. | ||
| - | < | + | < |
| ++++Lösung| | ++++Lösung| | ||
| <code python binaere_suche_rekursiv.py> | <code python binaere_suche_rekursiv.py> | ||
hof