Informatik · Klasse 12 · Datenstrukturen und Algorithmen · 1. Halbjahr

Suchverfahren: Binäre Suche und Hashing

Die Schülerinnen und Schüler implementieren die binäre Suche und lernen die Grundlagen von Hash-Tabellen kennen.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Modellieren und Implementieren
• KMK: Sekundarstufe II - Problemlösen und Handeln

Über dieses Thema

Die binäre Suche ist ein effizientes Verfahren, das auf vorsortierten Daten basiert und durch wiederholtes Teilen des Suchraums in zwei Hälften arbeitet. Schülerinnen und Schüler lernen, dass die Voraussetzung sortierte Daten sind, und implementieren den Algorithmus schrittweise: Vergleich des gesuchten Werts mit dem Mittelwert, Ausschluss der Hälfte und Wiederholung bis zum Fund. Hash-Tabellen ermöglichen durch Hash-Funktionen eine direkte Zuordnung von Schlüsseln auf Indizes, wobei Kollisionen mit Methoden wie verketteten Listen oder offener Adressierung gelöst werden.

Im KMK-Standard Sekundarstufe II zu Modellieren und Implementieren sowie Problemlösen und Handeln verbindet dieses Thema theoretische Analyse mit praktischer Programmierung. Schüler analysieren die Zeitkomplexität O(log n) der binären Suche im Vergleich zu linearer Suche und diskutieren, wie Hashing durchschnittlich O(1)-Zugriffe ermöglicht, aber Worst-Case-Szenarien durch Kollisionen beeinträchtigt werden.

Aktives Lernen eignet sich hervorragend, da Schüler Algorithmen selbst coden und testen können. Simulationen mit realen Datensätzen machen Effizienzunterschiede messbar, Gruppenexperimente fördern das Verständnis von Kollisionen und Peer-Feedback stärkt das Problemlösen.

Leitfragen

1. Welche Rolle spielen vorsortierte Daten für die Effizienz von Suchalgorithmen?
2. Erklären Sie das Funktionsprinzip der binären Suche und ihre Voraussetzungen.
3. Analysieren Sie, wie Hash-Kollisionen in Hash-Tabellen behandelt werden können.

Lernziele

• Implementieren Sie die binäre Suche in einer Programmiersprache und demonstrieren Sie ihre Funktionsweise anhand von Beispieldaten.
• Analysieren Sie die Zeitkomplexität der binären Suche und vergleichen Sie sie mit der linearen Suche für verschiedene Datensatzgrößen.
• Erklären Sie das Konzept von Hash-Funktionen und ihre Rolle bei der schnellen Datenzuweisung in Hash-Tabellen.
• Beschreiben Sie mindestens zwei Strategien zur Behandlung von Hash-Kollisionen, wie z.B. Verkettung oder offene Adressierung.
• Entwerfen Sie eine einfache Hash-Tabelle und implementieren Sie die Einfüge- und Suchoperationen unter Berücksichtigung von Kollisionen.

Bevor es losgeht

Grundlagen der Programmierung: Arrays und Listen

Warum: Schüler müssen verstehen, wie Daten in sequenziellen Strukturen gespeichert werden, um Algorithmen darauf anwenden zu können.

Algorithmen: Einführung und Komplexität

Warum: Ein grundlegendes Verständnis von Algorithmen und deren Effizienz (z.B. O-Notation) ist notwendig, um die Vorteile der binären Suche und Hashing zu erfassen.

Schlüsselvokabular

Binäre Suche	Ein Suchalgorithmus, der auf sortierten Listen angewendet wird, indem der Suchbereich wiederholt halbiert wird, bis das Element gefunden ist oder der Bereich leer ist.
Hash-Funktion	Eine Funktion, die einen Schlüssel in einen Index umwandelt, der als Speicherort in einer Hash-Tabelle dient.
Hash-Tabelle	Eine Datenstruktur, die Schlüssel-Wert-Paare speichert und Hash-Funktionen verwendet, um den Index für jeden Schlüssel schnell zu berechnen.
Hash-Kollision	Ein Zustand, bei dem zwei unterschiedliche Schlüssel von der Hash-Funktion auf denselben Index abgebildet werden.
Lineare Suche	Ein einfacher Suchalgorithmus, der eine Liste Element für Element durchläuft, bis das gesuchte Element gefunden wird oder die Liste endet.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Binäre Suche funktioniert auch mit unsortierten Daten.

Was Sie stattdessen lehren sollten

Viele glauben, die Halbierung spare immer Zeit, unabhängig von der Sortierung. Active Learning hilft: Schüler sortieren Listen manuell und vergleichen Suchzeiten, entdecken durch Experimente die Notwendigkeit und lernen Messmethoden.

Häufige Fehlvorstellung

Hash-Tabellen haben immer konstante O(1)-Zeit.

Was Sie stattdessen lehren sollten

Schüler übersehen Kollisionen und Worst-Case. Gruppensimulationen mit vielen Kollisionen zeigen Verlangsamungen; Peer-Diskussionen klären, wie gute Hash-Funktionen minimieren.

Häufige Fehlvorstellung

Hash-Funktionen sind beliebig und unwichtig.

Was Sie stattdessen lehren sollten

Viele denken, jede Division reicht. Praktische Tests verschiedener Funktionen in Pairs offenbaren Clusterbildung; aktive Iteration verbessert Verständnis.

Ideen für aktives Lernen

Pair Programming: Binäre Suche implementieren

Paare sortieren eine Liste von 20 Zahlen und coden die binäre Suche in Python. Sie testen mit verschiedenen Werten und messen Vergleichsschritte. Abschließend vergleichen sie mit linearer Suche.

45 Min.·Partnerarbeit

Small Group Simulation: Hash-Tabelle bauen

Gruppen erstellen eine Hash-Tabelle mit 10 Slots per Hand auf Papier, wenden eine einfache Hash-Funktion an und lösen Kollisionen durch Verkettung. Sie fügen 15 Elemente ein und analysieren Auslastung.

30 Min.·Kleingruppen

Whole Class Challenge: Effizienzvergleich

Klasse teilt sich in Teams: Ein Team simuliert lineare Suche, das andere binäre. Mit großen Listen (100 Elemente) zählen sie Schritte und präsentieren Ergebnisse auf dem Beamer.

50 Min.·Ganze Klasse

Individual Experiment: Kollisionsstrategien

Jeder Schüler testet chaining vs. linear probing in Code mit zufälligen Daten. Er notiert Insert- und Search-Zeiten und diskutiert Vor- Nachteile.

25 Min.·Einzelarbeit

Bezüge zur Lebenswelt

• Datenbankmanagementsysteme wie MySQL oder PostgreSQL verwenden Hashing und binäre Suchbäume (eine verwandte Struktur) für die Indizierung von Daten, um Abfragen wie 'finde alle Kunden aus Berlin' schnell zu beantworten.
• Suchmaschinen wie Google nutzen fortschrittliche Hashing-Techniken, um riesige Mengen an Webseiten zu indizieren und relevante Suchergebnisse in Millisekunden zu liefern.
• Betriebssysteme nutzen Hash-Tabellen zur Verwaltung von Prozess-IDs oder zur schnellen Suche nach Dateien im Dateisystem, was die Systemleistung erheblich verbessert.

Ideen zur Lernstandserhebung

Kurze Überprüfung

Geben Sie den Schülern eine kleine, sortierte Liste von Zahlen und einen Suchwert. Bitten Sie sie, die Schritte der binären Suche auf Papier nachzuvollziehen und den Mittelwert bei jedem Schritt zu notieren, bis das Element gefunden ist oder ausgeschlossen wird.

Diskussionsfrage

Stellen Sie die Frage: 'Unter welchen Umständen wäre die binäre Suche einer linearen Suche deutlich unterlegen, auch wenn die Daten sortiert sind?' Diskutieren Sie die Antworten und leiten Sie zur Bedeutung der Datenmenge und der Implementierungskosten über.

Lernstandskontrolle

Bitten Sie die Schüler, auf einem Zettel zu erklären, warum eine Hash-Kollision ein Problem darstellt und nennen Sie eine Methode, wie diese behoben werden kann. Bewerten Sie die Klarheit der Erklärung und die Korrektheit der genannten Methode.

Häufig gestellte Fragen

Wie funktioniert die binäre Suche genau?

Die binäre Suche startet mit vorsortierten Daten, vergleicht den gesuchten Wert mit dem Mittelwert des Arrays und schließt je eine Hälfte aus. Dieser Prozess wiederholt sich logarithmisch, bis der Wert gefunden oder ausgeschlossen ist. In der Oberstufe implementieren Schüler das in Code, analysieren Schleifenschritte und verknüpfen mit Big-O-Notation für tieferes Verständnis der Effizienz.

Was sind Hash-Kollisionen und wie behebt man sie?

Hash-Kollisionen entstehen, wenn verschiedene Schlüssel denselben Index erzeugen. Lösungen umfassen Verkettete Listen (Chaining), bei denen Kollisionen in Listen am Slot hängen, oder offene Adressierung mit Probing. Schüler testen Strategien praktisch, messen Performance und lernen, dass Load-Faktoren unter 0,7 optimal sind, um Degradation zu vermeiden.

Wie kann active learning Binäre Suche und Hashing vermitteln?

Active Learning aktiviert Schüler durch Pair Programming zur Implementierung und Gruppensimulationen von Hash-Tabellen. Sie messen reale Laufzeiten mit großen Datensätzen, lösen Kollisionen hands-on und diskutieren Ergebnisse. Diese Methoden machen abstrakte Komplexitäten greifbar, fördern Fehleranalyse und verbinden Theorie mit Praxis nach KMK-Standards.

Warum brauchen Suchalgorithmen vorsortierte Daten?

Vorsortierte Daten ermöglichen binärer Suche die effiziente Eliminierung von Hälften, was O(log n) ergibt statt O(n). Ohne Sortierung scheitert der Algorithmus. Schüler lernen das durch Vergleichsversuche: Sie sortieren Arrays und tracken Schritte, was Systems Thinking stärkt und Vorbereitungsaufwand rechtfertigt.