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.
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.
| n | linear (höchstens) | binär (höchstens) |
|---|---|---|
| 16 | 16 | 5 |
| 1.000 | 1.000 | 10 |
| 1.000.000 | 1.000.000 | 20 |
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 -1So lernst du hier
- AusprobierenDu änderst die Simulation selbst und beobachtest.
- Vorhersagen & lösenErst sagst du voraus, dann rechnest, klickst oder baust du – nicht nur Zahlen eintippen.
- Folgen sehenBei einem Fehler spielt die Simulation dein Ergebnis durch und zeigt die Abweichung.
- AufschreibenDu notierst in einem Satz, was dir aufgefallen ist – erst dann geht es weiter.
- 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.