Informatik · Klasse 6 · Algorithmen im Alltag · 1. Halbjahr

Suchalgorithmen

Die Schülerinnen und Schüler lernen verschiedene Suchalgorithmen kennen und vergleichen deren Effizienz bei der Suche in Datenmengen.

• KMK Bildungsstandards
• KMK: Sekundarstufe I - Algorithmen
• KMK: Sekundarstufe I - Problemlösen

Über dieses Thema

Suchalgorithmen helfen, Elemente in Listen schnell zu finden. Schüler in Klasse 6 lernen die lineare Suche kennen, bei der die Liste der Reihe nach durchgegangen wird, und die binäre Suche, die eine sortierte Liste durch Halbieren effizient durchsucht. Sie zählen Vergleiche, um die Effizienz zu vergleichen, und prüfen, wann die binäre Variante vorteilhaft ist: bei großen, sortierten Datenmengen braucht sie weniger Schritte.

Im KMK-Lehrplan zur Sekundarstufe I steht dieses Thema unter Algorithmen und Problemlösen. Es trainiert strukturiertes Denken, das Schüler im Alltag bei Apps oder Telefonbüchern anwenden. Die Key Questions fordern, lineare und binäre Suche zu differenzieren, Anwendungsbereiche zu nennen und eigene Algorithmen für unsortierte Listen zu bauen. So entsteht Verständnis für Bedingungen, unter denen ein Algorithmus optimal ist.

Aktive Lernansätze passen hervorragend, weil abstrakte Schritte durch greifbare Materialien wie Karten oder Würfel erlebbar werden. Schüler simulieren Suchen in Gruppen, messen Zeiten und diskutieren Ergebnisse: Das macht Effizienzunterschiede spürbar und festigt das Wissen langfristig.

Leitfragen

1. Differentiieren Sie zwischen linearer und binärer Suche und deren Anwendungsbereichen.
2. Analysieren Sie, unter welchen Bedingungen die binäre Suche der linearen Suche überlegen ist.
3. Konstruieren Sie einen Suchalgorithmus, um ein bestimmtes Element in einer unsortierten Liste zu finden.

Lernziele

• Differenzieren Sie zwischen linearer und binärer Suche hinsichtlich ihrer Funktionsweise und Anwendungsbereiche.
• Analysieren Sie die Anzahl der Vergleiche, die für die lineare und binäre Suche in Datensätzen unterschiedlicher Größe benötigt werden.
• Konstruieren Sie einen einfachen Suchalgorithmus zur Identifizierung eines Elements in einer unsortierten Liste.
• Bewerten Sie die Effizienz der binären Suche im Vergleich zur linearen Suche für sortierte Listen.
• Erklären Sie, warum die binäre Suche bei großen, sortierten Datenmengen vorteilhafter ist.

Bevor es losgeht

Grundlagen von Listen und Datenstrukturen

Warum: Schüler müssen verstehen, was eine Liste ist und wie Elemente darin organisiert sind, um Suchalgorithmen anwenden zu können.

Einführung in Algorithmen und Problemlösen

Warum: Ein grundlegendes Verständnis von Algorithmen als Schritt-für-Schritt-Anleitungen ist notwendig, um Suchalgorithmen zu begreifen.

Schlüsselvokabular

Lineare Suche	Ein Suchalgorithmus, der eine Liste Element für Element durchsucht, bis das gesuchte Element gefunden wird oder die Liste endet.
Binäre Suche	Ein Suchalgorithmus, der eine sortierte Liste durch wiederholtes Halbieren des Suchbereichs durchsucht. Sie ist deutlich schneller als die lineare Suche bei großen Listen.
Datenmenge	Eine Sammlung von Daten, die in einer Liste oder Tabelle organisiert ist und durchsucht werden kann.
Effizienz	Ein Maß dafür, wie schnell und mit wie vielen Schritten ein Algorithmus eine Aufgabe löst. Bei Suchen wird oft die Anzahl der Vergleiche gemessen.
Sortierte Liste	Eine Liste, deren Elemente in einer bestimmten Reihenfolge angeordnet sind, z. B. alphabetisch oder numerisch aufsteigend.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Die binäre Suche funktioniert immer schneller als die lineare.

Was Sie stattdessen lehren sollten

Die binäre Suche ist nur bei sortierten Listen effizient, sonst muss erst sortiert werden, was Zeit kostet. Aktive Simulationen mit Karten zeigen das: Schüler sortieren selbst und vergleichen Gesamtzeiten, korrigieren so ihr Bild durch eigene Erfahrung.

Häufige Fehlvorstellung

Bei der linearen Suche reicht es, nur einmal durch die Liste zu gehen.

Was Sie stattdessen lehren sollten

Jedes Element wird einzeln geprüft, bis das Gesuchte gefunden ist. Gruppenspiele mit realen Listen machen die Schrittzahl greifbar: Diskussionen helfen, den Unterschied zu binärer Halbierung zu verstehen.

Häufige Fehlvorstellung

Suchalgorithmen brauchen immer einen Computer.

Was Sie stattdessen lehren sollten

Algorithmen sind schrittweise Anweisungen, die manuell ausführbar sind. Hände-on-Aktivitäten mit physischen Objekten beweisen das: Schüler führen Suchen aus und sehen, wie Denken unabhängig von Technik arbeitet.

Ideen für aktives Lernen

Stationenrotation: Lineare vs. binäre Suche

Richten Sie vier Stationen ein: kleine unsortierte Liste (lineare Suche), große sortierte Liste (binäre Suche), Zeitmessung mit Stoppuhr, Protokollbögen. Gruppen rotieren alle 10 Minuten, notieren Vergleiche und ziehen Schlüsse. Abschließende Plenumdiskussion.

45 Min.·Kleingruppen

Paararbeit: Eigener Algorithmus bauen

Paare erhalten unsortierte Kartenlisten und konstruieren einen Suchpfad. Sie testen gegenseitig, zählen Schritte und optimieren. Präsentation der besten Varianten in der Klasse.

30 Min.·Partnerarbeit

Ganzer-Klasse-Spiel: Suchwettbewerb

Teilen Sie die Klasse in Teams auf. Ein Schüler versteckt ein Objekt in einer nummerierten Liste, andere suchen linear oder binär. Teams vergleichen Erfolgszeiten bei wachsenden Listen.

35 Min.·Ganze Klasse

Individuell: Computer-Simulation

Schüler nutzen eine einfache App oder Scratch-Programm, um Suchalgorithmen zu programmieren und mit Datenmengen zu testen. Sie notieren Effizienzwerte in einem Arbeitsblatt.

25 Min.·Einzelarbeit

Bezüge zur Lebenswelt

• Die binäre Suche wird in Computerprogrammen verwendet, die große Datenbanken durchsuchen, wie z. B. die Suche nach einem bestimmten Buch in der Online-Bibliothek der Deutschen Nationalbibliothek.
• Wenn Sie in einer App wie 'Spotify' nach einem bestimmten Song suchen, verwendet die App oft eine Variante der binären Suche, um den Song schnell in ihrer umfangreichen Musikbibliothek zu finden, vorausgesetzt, die Liste ist sortiert.
• Die lineare Suche kann in einfachen Anwendungen wie dem Durchsuchen einer kurzen Einkaufsliste auf dem Handy eingesetzt werden, wenn die Reihenfolge der Artikel keine Rolle spielt.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Geben Sie jedem Schüler eine Karte mit einer sortierten Liste von 5 Zahlen und einer Zielzahl. Bitten Sie die Schüler, auf der Rückseite die Schritte einer binären Suche aufzulisten, um die Zahl zu finden, und die Anzahl der benötigten Vergleiche anzugeben.

Kurze Überprüfung

Zeigen Sie eine unsortierte Liste von Namen an. Stellen Sie die Frage: 'Wenn Sie den Namen 'Meier' suchen, welche Art von Suche würden Sie hier anwenden und warum? Beschreiben Sie kurz die ersten beiden Schritte dieser Suche.'

Diskussionsfrage

Diskutieren Sie in Kleingruppen: 'Stellen Sie sich vor, Sie haben eine Liste mit 1000 Namen von Teilnehmern für ein Schulfest. Welche Suchmethode wäre besser geeignet, um schnell einen bestimmten Namen zu finden, und warum? Welche Informationen über die Liste sind dafür wichtig?'

Häufig gestellte Fragen

Wie unterscheide ich lineare und binäre Suche im Unterricht?

Erklären Sie die lineare Suche als einfaches Durchgehen von links nach rechts, ideal für kleine unsortierte Listen. Die binäre Suche halbieren Sie visuell mit einer sortierten Karte: Mitte prüfen, Hälfte streichen. Lassen Sie Schüler beides mit 10-50 Elementen testen, zählen Sie Vergleiche: So wird klar, dass binär bei großen Mengen log2(n) Schritte braucht, linear bis n.

Wann ist die binäre Suche der linearen überlegen?

Binäre Suche glänzt bei sortierten Listen mit mehr als 20 Elementen, da sie exponentiell effizienter ist: Statt 100 Vergleiche nur etwa 7. Voraussetzung ist Sortierung. Schüler analysieren das durch Tabellen: Bei unsortierten Listen gewinnt linear. Praxisbeispiele wie Wörterbücher festigen das.

Wie kann aktives Lernen beim Thema Suchalgorithmen helfen?

Aktives Lernen macht Algorithmen erfahrbar: Schüler manipulieren Kartenstaple, simulieren Halbierungen und messen reale Zeiten. In Gruppen diskutieren sie Optimierungen, was Missverständnisse abbaut und Motivation steigert. Solche Methoden verbinden Theorie mit Praxis, fördern Problemlösen und lassen Effizienzunterschiede intuitiv nachvollziehen, wie KMK-Standards es fordern.

Welche Materialien brauche ich für Suchalgorithmen?

Einfache Hilfsmittel reichen: Gedruckte Zahlen- oder Buchstabenlisten, Karten mit Symbolen, Stoppuhren und Protokollblätter. Für Digitales: Scratch oder GeoGebra-Applets. Passen Sie Listengrößen an (5-64 Elemente), um Effizienz zu zeigen. Das hält Vorbereitung minimal und Aktivitäten flexibel.