INFORMATIK · LABOR

Binäre Suche

Wie findet ein Computer eine Zahl unter einer Million mit nur 20 Vergleichen? Spiel den Algorithmus selbst – und sieh bei jedem Fehler, was deine Entscheidung auslösen würde.

  • ⏱ ca. 20 Min.
  • 🎯 Du kannst die binäre Suche Schritt für Schritt ausführen, ihre Laufzeit abschätzen und erklären, warum die Liste sortiert sein muss.

1Ausprobieren

Klicke auf „Nächster Vergleich“ und beobachte, wie lo und hi zusammenrücken. Vergleiche mit der linearen Suche.

2Selbst lösen

Erst nachdenken, dann antworten. Bei einem Fehler zeigt dir die Simulation, was dein Ergebnis bedeuten würde. Beschreibst du, was du siehst, läuft die richtige Lösung blass zum Vergleich mit. Bevor du es noch einmal versuchst, schreibst du kurz auf, was dir aufgefallen ist – dann geht es mit neuen Zahlen weiter.

3Zum Nachlesen

Erst ausprobieren, dann nachlesen: Hier steht, was hinter der Simulation steckt.

Die Idee

In einer sortierten Liste vergleichst du das gesuchte Element mit der Mitte. Ist die Mitte zu klein, kann das Ziel nur rechts davon stehen – die ganze linke Hälfte fällt weg. Ist sie zu groß, fällt die rechte Hälfte weg. Das wiederholst du mit dem Rest.

Wie viele Vergleiche?

Jeder Vergleich halbiert den Bereich. Bei n Elementen brauchst du im ungünstigsten Fall $\lfloor \log_2 n \rfloor + 1$ Vergleiche.

nlinear (höchstens)binär (höchstens)
16165
1.0001.00010
1.000.0001.000.00020

Als Programm (Python)

def suche(a, ziel):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == ziel:
            return mid
        elif a[mid] < ziel:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

So lernst du hier

  1. AusprobierenDu änderst die Simulation selbst und beobachtest.
  2. Vorhersagen & lösenErst sagst du voraus, dann rechnest, klickst oder baust du – nicht nur Zahlen eintippen.
  3. Folgen sehenBei einem Fehler spielt die Simulation dein Ergebnis durch und zeigt die Abweichung.
  4. AufschreibenDu notierst in einem Satz, was dir aufgefallen ist – erst dann geht es weiter.
  5. Neue ZahlenNach jedem Fehler kommt eine neue Variante. Wer sie löst, hat es verstanden – Raten hilft nicht.

Lehrplan: Algorithmen (Suchen und Sortieren). Informatik ist je nach Bundesland Pflicht-, Wahlpflicht- oder Wahlfach; die genaue Lehrplan-Zuordnung prüfen wir noch.

Für Lehrkräfte: Dieses Labor als Hausaufgabe aufgeben und die Nachweis-Codes der Klasse auswerten →

Fehler gefunden? Melde ihn uns – jede Simulation und jede Antwort wird von Code geprüft, aber Menschen machen trotzdem Fehler.