Pickles AcademyKostenlos starten

Binäre Suche – Übungen für die Klassen 8–10

Beispielaufgaben zum Thema Binäre Suche mit richtiger Antwort und Lösungsweg, von leicht bis schwer. In der App Pickles Academy bekommt ein Kind jedes Mal neue Aufgaben derselben Art, es kann sie also nicht auswendig lernen.

Fach
Informatik
Klasse
Klassen 8–10
Lernbereich
Informationssysteme

Aufgabentypen: Zahlenraten durch Halbieren

Regel: Binäre Suche

Rate immer die Mitte der übrigen Zahlen. Jede Antwort streicht etwa die Hälfte.

n Versuche reichen, wenn 2ⁿ − 1 mindestens so groß ist wie die Zahl der Möglichkeiten: 7 Zahlen 3, 15 Zahlen 4, 1000 Zahlen 10.

Beispiel: 1 bis 100: 2⁷ − 1 = 127 reicht, 2⁶ − 1 = 63 nicht → höchstens 7 Versuche

Achtung: Rate nicht der Reihe nach von vorn: Bei 100 Zahlen könnte das fast 100 Versuche dauern.

Beispielaufgaben

  1. Aufgabe 1 Leicht

    Ich denke mir eine ganze Zahl von 1 bis 31. Auf jeden Tipp antworte ich „größer“, „kleiner“ oder „richtig“. Wie viele Tipps brauchst du höchstens, wenn du immer die mittlere der übrigen Zahlen tippst?

    Lösung anzeigen
    Richtige Antwort: 5

    So geht es: Jeder Tipp halbiert den Rest mindestens: 2^4 = 16 ≤ 31 < 2^5 = 32, also 5 Tipps.

  2. Aufgabe 2 Normal

    Ich denke mir eine ganze Zahl von 1 bis 530. Auf jeden Tipp antworte ich „größer“, „kleiner“ oder „richtig“. Wie viele Tipps brauchst du höchstens, wenn du immer die mittlere der übrigen Zahlen tippst?

    Lösung anzeigen
    Richtige Antwort: 10

    So geht es: Jeder Tipp halbiert den Rest mindestens: 2^9 = 512 ≤ 530 < 2^10 = 1024, also 10 Tipps.

  3. Aufgabe 3 Schwer

    Ich denke mir eine ganze Zahl von 1 bis 80. Auf jeden Tipp antworte ich „größer“, „kleiner“ oder „richtig“. Du tippst immer die mittlere der übrigen Zahlen (bei gerader Anzahl die kleinere der beiden mittleren). Mit dem wievielten Tipp triffst du 54?

    Lösung anzeigen
    Richtige Antwort: 7

    So geht es: Tipps: 40, 60, 50, 55, 52, 53, 54.

Verwandte Themen

Alle Themen: Informatik

Weiter üben in der App

In einer Minute hat Ihr Kind einen eigenen Avatar und die erste Aufgabe. Kostenlos, werbefrei, Daten in der EU.

Kostenlos starten