| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung |
| gf_informatik:suchen_und_sortieren:binaersuche [2024-02-04 08:41] – [Aufgabe B3: Binäre Suche in Python] hof | gf_informatik:suchen_und_sortieren:binaersuche [2025-11-04 20:49] (aktuell) – gra |
|---|
| 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 |
| |
| ++++ | ++++ |
| |
| | <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> |
| |
| <code python binaere_suche.py> | <code python binaere_suche.py> |
| ++++ | ++++ |
| </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`. | - Ö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)]]. |
| - Importiere die das Modul `null79`, die 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. |
| - 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. |
| ++++ | ++++ |
| </nodisp> | </nodisp> |
| > | |
| #### Aufgabe B5: Zeitmessung mit linearer und binärer Suche | #### Aufgabe B5: Zeitmessung mit linearer und binärer Suche |
| Vergleiche die lineare Suche mit der binären Suche. Hierzu kannst du von Aufgabe B4 ausgehen (unter neuem Namen speichern): | Vergleiche die lineare Suche mit der binären Suche. Hierzu kannst du von Aufgabe B4 ausgehen (unter neuem Namen speichern): |
hof