Binäre Suche: So erklärt man sie Kindern
Binäre Suche am Beispiel des Zahlenratens: warum 7 Fragen für 100 Zahlen reichen, wie der Algorithmus Schritt für Schritt aussieht und welche Fehler Kinder machen.
Aktualisiert:
Die binäre Suche ist einer der ersten Algorithmen, bei denen das Kind sieht, dass ein schlauer Weg die Geduld schlägt. Am leichtesten fängt man mit einem Spiel an.
Das Spiel: Rate die Zahl
Denk dir eine Zahl von 1 bis 100. Das Kind rät, und du antwortest nur „zu klein“, „zu groß“ oder „Treffer“.
Am Anfang raten Kinder blind oder fragen der Reihe nach: 1, 2, 3… Frag dann, mit welcher Zahl man am besten anfängt, damit sicher möglichst viel wegfällt. Die Antwort ist die Mitte: 50.
Warum die Mitte
Nach der Frage nach 50 bleibt die Hälfte der Zahlen, egal wie die Antwort lautet. Nach der nächsten Frage ein Viertel. Der Bereich schrumpft so: 100, 50, 25, 13, 7, 4, 2, 1. Das sind sieben Fragen. Bei tausend Zahlen reichen zehn, bei einer Million zwanzig.
Fragt man der Reihe nach, braucht man im schlimmsten Fall hundert Fragen.
Der Algorithmus Schritt für Schritt
- Merk dir die beiden Enden des Bereichs:
linksundrechts. - Berechne die Mitte.
- Ist die Mitte die gesuchte Zahl, ist Schluss.
- Ist sie zu klein, schieb
linksdirekt hinter die Mitte. Ist sie zu groß, schiebrechtsdirekt vor die Mitte. - Geh zurück zu Schritt 2.
Das ist eine Schleife mit einer Entscheidung darin und zwei Variablen, die sich aufeinander zubewegen.
Wo man das braucht
- Ein Wort im gedruckten Wörterbuch suchen: Du schlägst es in der Mitte auf und weißt, in welche Richtung es weitergeht.
- Eine Seite im Buch suchen.
- Eine Körpergröße, einen Preis, ein Datum erraten.
Es gibt eine Bedingung: Die Daten müssen geordnet sein.
Typische Fehler
- Der Bereich wird nicht kleiner. Rückt
linksauf die Mitte und nicht hinter die Mitte, kann sich die Schleife endlos drehen. - Die Daten sind nicht sortiert. Dann verwirft der Algorithmus die Hälfte, in der die Antwort liegen konnte.
- Die gesuchte Zahl gibt es nicht. Die Schleife muss enden, wenn
linksanrechtsvorbei ist.
In Looponi
Die binäre Suche ist einer der Algorithmen auf dem Pfad für die Klassen 7–8. Die Schülerin oder der Schüler legt sie als Flussdiagramm, tippt, wie viele Runden die Schleife dreht, und sieht zu, wie sich die Enden des Bereichs bei jedem Schritt näherkommen.
Häufige Fragen
Was ist die binäre Suche?
Eine Art, in geordneten Daten zu suchen, bei der nach jeder Frage die Hälfte der Möglichkeiten wegfällt. Wir prüfen die Mitte und gehen nach links oder nach rechts.
Wie viele Fragen braucht man, um eine Zahl von 1 bis 100 zu erraten?
Höchstens 7. Jede Frage halbiert den Bereich: 100, 50, 25, 13, 7, 4, 2, 1.
Warum müssen die Daten geordnet sein?
Weil nur dann die Antwort „zu klein“ oder „zu groß“ sagt, welche Hälfte wegfallen kann. In ungeordneten Daten muss man der Reihe nach prüfen.
Ab welchem Alter kann man das lehren?
Das Zahlenraten versteht schon ein achtjähriges Kind. Den Algorithmus selbst mit Variablen führt man am besten mit etwa 12–13 Jahren ein.