Suchalgorithmen: Linear und Binär

Aktive Lernformen eignen sich besonders gut, um Suchalgorithmen zu verstehen, weil Schüler die Unterschiede zwischen linearer und binärer Suche nicht nur theoretisch nachvollziehen, sondern durch eigenes Handeln erfahren können. Die manuelle Simulation und der direkte Vergleich zeigen, warum Effizienz von Datenmenge und Vorbereitung abhängt. So wird Abstraktes greifbar und nachhaltig verankert.

• Klasse 11
• Informatik in der Oberstufe: Algorithmen, Daten und Gesellschaft
• 4 Aktivitäten
• 30 Min.–50 Min.

Lernziele

1. Vergleichen Sie die Laufzeitkomplexität von linearer Suche und binärer Suche für gegebene Datensatzgrößen.
2. Analysieren Sie die Auswirkungen der Vorsortierung von Daten auf die Effizienz von Suchalgorithmen.
3. Begründen Sie die Auswahl eines Suchalgorithmus (linear oder binär) basierend auf spezifischen Anwendungsbedingungen und Dateneigenschaften.
4. Implementieren Sie sowohl die lineare als auch die binäre Suchfunktion in einer Programmiersprache Ihrer Wahl.
5. Bewerten Sie die Praktikabilität von Bubble Sort als Sortierverfahren im Kontext der binären Suche.

Planspiel

⏱ 30 Min.·Kleingruppen

Planspiel: Manuelle Suche

Teilen Sie Karten mit Zahlen an Gruppen aus. Führen Sie lineare Suche durch Sequentielles Durchsuchen durch, notieren Sie Schritte. Wiederholen Sie mit sortierter Liste und binärer Suche, vergleichen Sie die Anzahl der Prüfungen. Diskutieren Sie Ergebnisse in der Gruppe.

Vorbereitung & Details

Wie verändert die Vorsortierung von Daten die Geschwindigkeit einer Suche?

Moderationstipp: Während der manuellen Suche lassen Sie Schüler die Anzahl der Schritte laut mitzählen, um die O(n)-Komplexität direkt erlebbar zu machen.

Setup: Flexibler Raum für verschiedene Gruppenstationen

Materials: Rollenkarten mit Zielen und Ressourcen, Spielwährung oder Token, Rundenprotokoll

• Anwenden
• Analysieren
• Bewerten
• Erschaffen
• Sozialbewusstsein
• Entscheidungsfähigkeit

Lernen an Stationen

⏱ 45 Min.·Partnerarbeit

Coding Challenge: Python-Implementierung

Schüler implementieren lineare und binäre Suche in Python. Testen Sie mit Listen unterschiedlicher Größe und Sortierung. Messen Sie Laufzeiten mit time-Modul und plotten Sie Grafiken. Präsentieren Sie beste Fälle.

Vorbereitung & Details

Vergleichen Sie die Effizienz von linearer und binärer Suche unter verschiedenen Bedingungen.

Moderationstipp: Fordern Sie in der Coding Challenge die Schüler auf, ihre Implementierungen mit einer Stoppuhr zu testen, um den Unterschied zwischen O(n) und O(log n) quantitativ zu erfassen.

Setup: Im Raum verteilte Tische/Stationen

Materials: Stationskarten mit Arbeitsanweisungen, Unterschiedliche Materialien je Station, Timer für die Rotation

• Erinnern
• Verstehen
• Anwenden
• Analysieren
• Selbststeuerung
• Beziehungsfähigkeit

Lernen an Stationen

⏱ 50 Min.·Kleingruppen

Effizienz-Wettbewerb

Erstellen Sie große Listen mit Zufallsdaten. Gruppen sortieren mit Bubble Sort, dann suchen. Wettkampf um schnellste Gesamtlaufzeit. Analysieren Sie, warum lineare Suche bei kleinen Listen gewinnt.

Vorbereitung & Details

Begründen Sie, wann eine lineare Suche trotz geringerer Effizienz die bessere Wahl sein kann.

Moderationstipp: Beim Effizienz-Wettbewerb verteilen Sie Listen unterschiedlicher Größe, um zu zeigen, dass lineare Suche bei kleinen Datenmengen schneller sein kann.

Setup: Im Raum verteilte Tische/Stationen

Materials: Stationskarten mit Arbeitsanweisungen, Unterschiedliche Materialien je Station, Timer für die Rotation

• Erinnern
• Verstehen
• Anwenden
• Analysieren
• Selbststeuerung
• Beziehungsfähigkeit

Lernen an Stationen

⏱ 35 Min.·Ganze Klasse

Visualisierung: Schritt-für-Schritt

Nutzen Sie Online-Tools wie VisuAlgo. Schüler führen binäre Suche schrittweise aus, markieren Suchraum. Erstellen Sie Screenshots und erklären Sie in Plenum, warum Halbierung effizient ist.

Vorbereitung & Details

Wie verändert die Vorsortierung von Daten die Geschwindigkeit einer Suche?

Moderationstipp: Lassen Sie bei der Visualisierung die Schüler die Teilungsschritte der binären Suche an der Tafel nachzeichnen, um das Prinzip der Halbierung zu verinnerlichen.

Setup: Im Raum verteilte Tische/Stationen

Materials: Stationskarten mit Arbeitsanweisungen, Unterschiedliche Materialien je Station, Timer für die Rotation

• Erinnern
• Verstehen
• Anwenden
• Analysieren
• Selbststeuerung
• Beziehungsfähigkeit

Dieses Thema unterrichten

Erfahrene Lehrkräfte beginnen mit der Simulation, um das Grundprinzip beider Algorithmen zu verankern. Anschließend setzen sie die Implementierung in Code um, um die Brücke zwischen Theorie und Praxis zu schlagen. Wichtig ist, immer wieder auf die Voraussetzungen hinzuweisen: Binäre Suche braucht Sortierung, lineare Suche nicht. Vermeiden Sie es, die Komplexität nur abstrakt zu erklären – messbare Beispiele zeigen den Unterschied klarer.

Was Sie erwartet

Am Ende sollen die Schüler den Unterschied zwischen linearer und binärer Suche nicht nur erklären, sondern auch praktisch anwenden können. Sie erkennen, wann welche Methode sinnvoll ist und können die Zeitkomplexität mit eigenen Messungen begründen. Die Diskussion zeigt, dass sie Bedingungen für Effizienz kritisch hinterfragen.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Während des Effizienz-Wettbewerbs beobachten Sie, dass einige Schüler glauben, binäre Suche sei immer schneller.

Was Sie stattdessen lehren sollten

Führen Sie nach dem Wettbewerb eine kurze Diskussion an, in der die Schüler ihre Messergebnisse vergleichen. Lassen Sie sie erklären, warum lineare Suche bei kleinen Listen (z.B. unter 20 Elementen) oft schneller ist und welche Rolle die Vorbereitungszeit von Bubble Sort spielt.

Häufige Fehlvorstellung

Während der Python-Implementierung hören Sie Schüler sagen, die Zeitkomplexität hänge vom verwendeten Computer ab.

Was Sie stattdessen lehren sollten

Lassen Sie die Schüler ihre Programme mit Listen unterschiedlicher Größen (z.B. 1.000, 10.000, 100.000 Elemente) ausführen und die Laufzeiten notieren. Zeigen Sie, dass sich das Verhältnis der Laufzeiten (z.B. 10:1) unabhängig vom Rechner bestätigt.

Häufige Fehlvorstellung

Während der Simulation mit Karten wird Bubble Sort als irrelevant für Suchalgorithmen abgetan.

Was Sie stattdessen lehren sollten

Lassen Sie die Schüler die sortierte Liste nach dem Bubble-Sort-Schritt mit der ursprünglichen vergleichen. Fordern Sie sie auf, die Anzahl der Vertauschungen zu zählen und zu berechnen, wie sich diese auf die Gesamtzeit auswirken, wenn eine binäre Suche folgt.

Ideen zur Lernstandserhebung

Kurze Überprüfung

Nach der Simulation 'Manuelle Suche' geben Sie den Schülern eine unsortierte Liste mit 15 Zahlen und eine Zielzahl. Lassen Sie sie die Schritte der linearen Suche aufschreiben und die Anzahl der Vergleiche notieren. Sammeln Sie die Ergebnisse und besprechen Sie, warum die Zahl variieren kann.

Diskussionsfrage

Nach dem Effizienz-Wettbewerb stellen Sie die Frage: 'Wann wäre eine lineare Suche trotz ihrer geringeren Effizienz die bessere Wahl?' Lassen Sie die Schüler Beispiele wie einmalige Suchen in kleinen Listen oder Suchen in unsortierbaren Daten nennen und begründen, warum binäre Suche hier ungeeignet ist.

Lernstandskontrolle

Nach der Visualisierung 'Schritt-für-Schritt' bitten Sie die Schüler, auf einem Zettel zwei Szenarien zu beschreiben: Ein Szenario, in dem die binäre Suche klar überlegen ist, und eines, in dem die lineare Suche ausreicht. Sie sollen jeweils kurz begründen, warum die Vorbereitung (Sortierung) oder die Datenmenge eine Rolle spielt.

Erweiterungen & Unterstützung

• Fordern Sie Schüler auf, eine eigene Liste mit 100 zufälligen Zahlen zu generieren und beide Suchverfahren zu implementieren. Sie sollen messen, ab welcher Listengröße die binäre Suche schneller wird.
• Für Schüler mit Schwierigkeiten: Lassen Sie sie zunächst eine bereits sortierte Liste linear durchsuchen, um zu verstehen, warum Sortierung für binäre Suche nötig ist.
• Vertiefung: Lassen Sie Schüler untersuchen, wie sich der Overhead von Bubble Sort auf die Gesamtzeit auswirkt, wenn er vor einer binären Suche ausgeführt wird.

Schlüsselvokabular

Lineare Suche	Ein Suchalgorithmus, der eine Liste Element für Element durchläuft, bis das gesuchte Element gefunden wird oder die Liste endet. Seine Zeitkomplexität ist O(n).
Binäre Suche	Ein Suchalgorithmus, der eine vorsortierte Liste verwendet und den Suchbereich bei jedem Schritt halbiert. Seine Zeitkomplexität ist O(log n).
Zeitkomplexität	Ein Maß dafür, wie sich die Laufzeit eines Algorithmus mit der Größe der Eingabe (z. B. der Anzahl der Elemente in einer Liste) verändert.
Vorsortierung	Der Prozess, eine Datenmenge vor der Anwendung eines Algorithmus (wie der binären Suche) in eine bestimmte Reihenfolge zu bringen, um dessen Effizienz zu verbessern.
Bubble Sort	Ein einfacher Sortieralgorithmus, der wiederholt benachbarte Elemente vergleicht und vertauscht, wenn sie in der falschen Reihenfolge sind. Seine Zeitkomplexität ist typischerweise O(n²).