Suchverfahren

Lineare Suche, binäre Suche und Hashing — drei fundamentale Strategien zum Finden von Daten, visuell erklärt und in Python implementiert.

Klasse 11 · Informatik · 90 min

Modul 01

Die drei Suchstrategien

Wie findet man einen bestimmten Wert in einer Datensammlung? Es gibt drei grundsätzlich verschiedene Ansätze — jeder mit eigenen Stärken, Schwächen und Voraussetzungen.

🔍 Lineare Suche

Element für Element durchgehen, bis der Suchwert gefunden wird — oder das Ende erreicht ist.

↓ Details anzeigen

Prinzip: Vergleiche nacheinander jedes Element der Liste mit dem Suchwert. Beim ersten Treffer → Abbruch. Kein Treffer nach dem letzten Element → nicht gefunden.

Voraussetzung: Keine! Die Daten müssen nicht sortiert sein.

Zeitkomplexität: O(n) — im schlimmsten Fall muss jedes Element geprüft werden.

Python def lineare_suche(liste, suchwert): for i in range(len(liste)): if liste[i] == suchwert: return i # Index gefunden return -1 # Nicht gefunden

Analogie: Wie wenn du ein Buch in einem unsortieren Bücherregal suchst — du musst jedes Buch einzeln anschauen.

⚡ Binäre Suche

In jedem Schritt die Hälfte der verbleibenden Elemente ausschließen — extrem schnell bei sortierten Daten.

↓ Details anzeigen

Prinzip: Vergleiche den Suchwert mit dem mittleren Element. Ist er kleiner → suche links weiter. Ist er größer → suche rechts weiter. Wiederhole, bis gefunden oder Bereich leer.

Voraussetzung: Die Daten müssen sortiert sein!

Zeitkomplexität: O(log n) — bei jeder Iteration halbiert sich der Suchbereich.

Python def binaere_suche(liste, suchwert): links, rechts = 0, len(liste) - 1 while links <= rechts: mitte = (links + rechts) // 2 if liste[mitte] == suchwert: return mitte elif liste[mitte] < suchwert: links = mitte + 1 else: rechts = mitte - 1 return -1

Analogie: Wie das Nachschlagen im Telefonbuch — man schlägt in der Mitte auf und weiß sofort, in welcher Hälfte der Name steckt.

#️⃣ Hashing

Den Speicherort direkt berechnen — Zugriff in konstanter Zeit, unabhängig von der Datenmenge.

↓ Details anzeigen

Prinzip: Eine Hashfunktion berechnet aus dem Suchwert direkt den Index (die Position) in einer Tabelle. Man greift also sofort auf die richtige Stelle zu, ohne zu suchen.

Voraussetzung: Eine geeignete Hashfunktion und eine Hashtabelle (Array fester Größe). Kollisionen müssen behandelt werden.

Zeitkomplexität: O(1) im Durchschnitt — Zugriff in konstanter Zeit!

Python def hash_einfuegen(tabelle, wert): index = wert % len(tabelle) # Hashfunktion: Modulo tabelle[index] = wert def hash_suche(tabelle, wert): index = wert % len(tabelle) if tabelle[index] == wert: return index return -1

Kollision: Wenn zwei Werte denselben Index berechnen (z.B. 15 % 10 = 5 und 25 % 10 = 5). Lösungen: Verkettung (Liste pro Bucket) oder offene Adressierung (nächster freier Platz).

Analogie: Wie ein Spind-System — deine Spindnummer ergibt sich direkt aus deinem Nachnamen.

Vergleich auf einen Blick

Lineare Suche

  • O(n) Zeitkomplexität
  • Keine Vorbedingung
  • Einfach zu implementieren
  • Langsam bei großen Daten
  • Gut für kleine / unsortierte Listen

Binäre Suche

  • O(log n) Zeitkomplexität
  • Daten müssen sortiert sein
  • Divide-and-Conquer
  • Sehr effizient
  • Standard für sortierte Arrays

Hashing

  • O(1) im Durchschnitt
  • Braucht Hashtabelle
  • Kollisionsbehandlung nötig
  • Schnellster Zugriff
  • Extra Speicherplatz nötig

Ablauf der binären Suche

Sortierte Liste
→
Mitte berechnen
→
Vergleichen
→
Hälfte eliminieren
→
Wiederholen

Modul 02

Interaktive Visualisierung

Beobachte Schritt für Schritt, wie die drei Suchverfahren arbeiten. Wähle einen Suchwert und verfolge jeden Vergleich live.

Bereit. Klicke "Starten" um die lineare Suche zu beginnen.
Bereit. Die Liste ist sortiert. Klicke "Starten".

Hashfunktion: h(x) = x mod 10 (Tabellengröße = 10)

Bereit. Füge Werte ein und beobachte die Hashfunktion.

Modul 03

Interaktive Aufgaben

Teste dein Verständnis der Suchverfahren mit diesen interaktiven Übungen.

Aufgabe 1: Komplexitätsvergleich

Verschiebe den Regler und beobachte, wie sich die maximale Schrittzahl bei den drei Verfahren verändert.


101001K10K100K1M10M

Lineare Suche

O(n)
1.000
max. Vergleiche

Binäre Suche

O(log n)
10
max. Vergleiche

Hashing

O(1)
1
Zugriffe (ideal)

Aufgabe 2: Richtig oder Falsch?

Klicke auf eine Aussage, um die Antwort aufzudecken.

Aufgabe 3: Schritte sortieren

Bringe die Schritte der binären Suche in die richtige Reihenfolge! Ziehe die Elemente mit der Maus (oder per Touch).

Aufgabe 4: Python-Tracing

Führe den Python-Code im Kopf aus. Wie viele Vergleiche braucht die binäre Suche, um den Wert 67 in der Liste zu finden? Trage deine Antwort ein.

Python — Trace liste = [3, 7, 12, 15, 23, 31, 42, 56, 67, 89] suchwert = 67 links, rechts = 0, 9 vergleiche = 0 while links <= rechts: mitte = (links + rechts) // 2 vergleiche += 1 if liste[mitte] == suchwert: print(f"Gefunden bei Index {mitte}, {vergleiche} Vergleiche") break elif liste[mitte] < suchwert: links = mitte + 1 else: rechts = mitte - 1

Lernziele — Selbstcheck

Hake ab, was du bereits verstanden hast:

0 / 8 erledigt

Modul 04

Wissensquiz

20 Fragen in vier Schwierigkeitsstufen — teste dein Wissen über Suchverfahren.

0 / 20
Punkte erreicht

Modul 05

Glossar — Fachbegriffe

Klicke auf eine Karte, um die Definition aufzudecken.

Diskussion im Kurs

„Hashing hat eine Zeitkomplexität von O(1) — ist es also immer besser als binäre Suche? Diskutiert Situationen, in denen binäre Suche trotzdem vorzuziehen wäre. Denkt dabei an Speicherverbrauch, sortierte Ausgabe, Worst-Case-Verhalten und die Wahl der Hashfunktion."