Binäre Suche und Effizienz

Aktive Lernmethoden wie Paarprogrammierung oder physische Experimente machen die abstrakte Komplexität der binären Suche für Schülerinnen und Schüler greifbar. Durch die Kombination von Code, Bewegung und Wettbewerb erkennen sie selbst, warum dieser Algorithmus effizient ist und welche Rolle Sortierung dabei spielt.

• Klasse 9
• Digitale Welten Gestalten: Informatik und Gesellschaft
• 4 Aktivitäten
• 30 Min.–50 Min.

Lernziele

1. Vergleichen Sie die Anzahl der notwendigen Vergleiche für die binäre Suche und die lineare Suche bei verschiedenen Datensatzgrößen.
2. Analysieren Sie die Bedingungen, unter denen die binäre Suche angewendet werden kann, und identifizieren Sie Fälle, in denen sie nicht geeignet ist.
3. Begründen Sie, warum eine sortierte Datenstruktur die Effizienz der binären Suche ermöglicht.
4. Implementieren Sie den Algorithmus der binären Suche in einer Programmiersprache Ihrer Wahl.
5. Bewerten Sie die Laufzeitunterschiede zwischen binärer und linearer Suche durch Messung und grafische Darstellung.

Problemorientiertes Lernen

⏱ 45 Min.·Partnerarbeit

Paarprogrammierung: Binäre vs. Lineare Suche

In Paaren implementieren Schüler beide Algorithmen in Python für eine Liste von 1000 Zahlen. Sie messen die Vergleichszahlen mit print-Anweisungen und vergleichen die Ergebnisse in einer Tabelle. Abschließend diskutieren sie den Effizienzunterschied.

Vorbereitung & Details

Vergleichen Sie die Effizienz der binären Suche mit der linearen Suche.

Moderationstipp: Fordern Sie die Teams in der Paarprogrammierung auf, ihre Implementierungen direkt mit Laufzeitmessungen zu testen und zu dokumentieren, um den Effizienzunterschied sichtbar zu machen.

Setup: Gruppentische mit Zugang zu Recherchequellen

Materials: Dokumentation des Problemszenarios, KWL-Tabelle (Wissen, Wollen, Lernen) oder Inquiry-Framework, Ressourcenpool / Handapparat, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Entscheidungsfähigkeit
• Selbststeuerung
• Beziehungsfähigkeit

Lernen an Stationen

⏱ 50 Min.·Kleingruppen

Lernen an Stationen: Physische Suche

Richten Sie Stationen ein: Sortieren von Karten, lineare Suche, binäre Suche und Effizienzvergleich mit Stoppuhr. Gruppen rotieren, protokollieren Suchzeiten und ziehen Rückschlüsse auf Skalierbarkeit.

Vorbereitung & Details

Analysieren Sie die Voraussetzungen für die Anwendung der binären Suche.

Moderationstipp: Stellen Sie bei den Stationsarbeiten sicher, dass die Schülerinnen und Schüler die Sortiervoraussetzung durch das Scheitern mit unsortierten Karten selbst erleben und diskutieren.

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

Problemorientiertes Lernen

⏱ 35 Min.·Kleingruppen

Klassenwettbewerb: Such-Challenge

Teilen Sie eine große sortierte Liste aus. Teams wählen Strategie (linear oder binär), suchen Begriffe und messen kollektiv Zeiten. Die Klasse grafisch auswertend, gewinnt das effizienteste Team.

Vorbereitung & Details

Begründen Sie, warum die Sortierung von Daten die Grundlage für schnelle Suche ist.

Moderationstipp: Legen Sie beim Klassenwettbewerb klare Regeln für die Laufzeitmessung fest, damit die Ergebnisse vergleichbar sind und die Effizienzunterschiede deutlich werden.

Setup: Gruppentische mit Zugang zu Recherchequellen

Materials: Dokumentation des Problemszenarios, KWL-Tabelle (Wissen, Wollen, Lernen) oder Inquiry-Framework, Ressourcenpool / Handapparat, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Entscheidungsfähigkeit
• Selbststeuerung
• Beziehungsfähigkeit

Problemorientiertes Lernen

⏱ 30 Min.·Einzelarbeit

Individuell: Laufzeitanalyse

Jeder Schüler erzeugt Listen unterschiedlicher Größe, codet binäre Suche und plottet Vergleiche mit Matplotlib. Sie begründen Vor- und Nachteile gegenüber linearer Suche.

Vorbereitung & Details

Vergleichen Sie die Effizienz der binären Suche mit der linearen Suche.

Moderationstipp: Ermutigen Sie die Lernenden während der Laufzeitanalyse, ihre Messergebnisse in Tabellen oder Diagrammen festzuhalten, um Muster zu erkennen.

Setup: Gruppentische mit Zugang zu Recherchequellen

Materials: Dokumentation des Problemszenarios, KWL-Tabelle (Wissen, Wollen, Lernen) oder Inquiry-Framework, Ressourcenpool / Handapparat, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Entscheidungsfähigkeit
• Selbststeuerung
• Beziehungsfähigkeit

Dieses Thema unterrichten

Erfahrene Lehrkräfte beginnen mit konkreten, greifbaren Beispielen, bevor sie zur abstrakten Laufzeitanalyse übergehen. Sie vermeiden es, den Algorithmus nur theoretisch zu erklären, und setzen stattdessen auf Hands-on-Aktivitäten, die die Schülerinnen und Schüler aktiv einbinden. Wichtig ist, dass die Lernenden selbst die Effizienzunterschiede erleben und nicht nur hören.

Was Sie erwartet

Am Ende der Einheit verstehen die Lernenden, dass die binäre Suche bei sortierten Daten logarithmische Laufzeiten erreicht, während die lineare Suche linear wächst. Sie können den Algorithmus implementieren, Laufzeiten vergleichen und die Notwendigkeit von Sortierung begründen.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Während der Stationenarbeit mit physischen Suchkarten beobachten Sie, dass einige Schülerinnen und Schüler die Karten absichtlich unsortiert lassen und trotzdem die binäre Suche anwenden.

Was Sie stattdessen lehren sollten

Bitten Sie die Lernenden, die unsortierten Karten systematisch zu sortieren und die binäre Suche erneut zu testen. Diskutieren Sie in der Gruppe, warum die Sortierung eine Voraussetzung ist und welche Schritte im Algorithmus ohne Sortierung scheitern würden.

Häufige Fehlvorstellung

Während der Laufzeitanalyse in Kleingruppen äußern Schülerinnen und Schüler die Annahme, dass die binäre Suche immer genau doppelt so schnell ist wie die lineare Suche.

Was Sie stattdessen lehren sollten

Fordern Sie die Gruppen auf, ihre Laufzeitmessungen in Diagrammen darzustellen und zu vergleichen. Zeigen Sie, dass der Effizienzvorteil exponentiell mit der Datenmenge wächst, und diskutieren Sie, warum die Annahme nicht für alle n gilt.

Häufige Fehlvorstellung

Während der Paarprogrammierung rechtfertigen einige Lernende lange, ineffiziente Implementierungen mit der Aussage, dass mehr Code immer besser sei.

Was Sie stattdessen lehren sollten

Lassen Sie die Teams ihre Laufzeiten messen und vergleichen Sie die Ergebnisse in der Klasse. Zeigen Sie, dass die binäre Suche trotz kürzerem Code effizienter ist, und diskutieren Sie, wie klare Struktur und einfache Algorithmen die Effizienz steigern.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Nach der Stationenarbeit erhalten die Schülerinnen und Schüler eine unsortierte und eine sortierte Liste mit je 10 Zahlen. Sie schätzen die Anzahl der Schritte für lineare und binäre Suche, um die Zahl 7 zu finden, und begründen ihre Schätzungen.

Kurze Überprüfung

Während des Klassenwettbewerbs wenden die Lernenden den Algorithmus der binären Suche auf eine sortierte Liste mit 16 Elementen an und dokumentieren jeden Vergleichsschritt. Die Lehrkraft sammelt die Schritte und vergleicht sie mit der maximalen Anzahl bei linearer Suche.

Diskussionsfrage

Nach der Paarprogrammierung diskutieren die Schülerinnen und Schüler in Kleingruppen, warum die binäre Suche effizienter ist als die lineare Suche. Sie nennen ein Alltagsbeispiel, bei dem schnelle Suche wichtig ist, und beschreiben, wie die Daten dafür sortiert sein könnten.

Erweiterungen & Unterstützung

• Fordern Sie schnelle Gruppen auf, eine optimierte Version der binären Suche zu entwickeln, die frühzeitig abbricht, wenn das gesuchte Element nicht gefunden werden kann.
• Unterstützen Sie leistungsschwächere Schülerinnen und Schüler durch vorgefertigte Code-Schnipsel oder Schritt-für-Schritt-Anleitungen für die Implementierung.
• Vertiefen Sie das Thema mit einer Diskussion über die Grenzen der binären Suche, z.B. bei dynamischen Daten oder großen Datensätzen mit begrenzter Speicherkapazität.

Schlüsselvokabular

Binäre Suche	Ein Suchalgorithmus, der in sortierten Listen wiederholt das mittlere Element mit dem gesuchten Wert vergleicht und den Suchbereich halbiert, bis das Element gefunden ist oder der Bereich leer ist.
Lineare Suche	Ein einfacher Suchalgorithmus, der nacheinander jedes Element einer Liste durchgeht, bis das gesuchte Element gefunden wird oder das Ende der Liste erreicht ist.
Laufzeitkomplexität	Ein Maß dafür, wie sich die Ausführungszeit eines Algorithmus mit zunehmender Größe der Eingabedaten verändert. Wird oft mit O-Notation (z.B. O(log n), O(n)) angegeben.
Sortierte Datenstruktur	Eine Anordnung von Daten, bei der die Elemente in einer bestimmten Reihenfolge (z.B. aufsteigend oder absteigend) angeordnet sind, was für effiziente Suchalgorithmen wie die binäre Suche notwendig ist.