In einem Spiel hat sich Alice eine Zahl zwischen 1 und 1000 gemerkt. Wir wollen sie unbedingt erfahren, aber Alice gibt sie nicht so leicht Preis. Sie ist zwar bereit, unsere Fragen zu beantworten, aber nur, wenn sie so formuliert sind, dass Alice mit „zu tief“, „zu hoch“ oder „Das ist die Zahl“ antworten kann. Wie können wir die Zahl trotzdem rasch herausfinden?

Nun, wir könnten natürlich sequentiell suchen. Das bedeutet, wir können der Reihe nach fragen: „Ist es die 1?“, „Ist es die 2?“, „Ist es die 3?“, und so weiter, aber im schlechtesten Fall würden wir tausend (und im Mittel 500) Fragen stellen müssen, und das wäre ganz schön zermürbend. Viel schneller und lustvoller ist da das binäre Suchen. Wir beginnen in der Mitte, also mit der Zahl 500. Falls Alice sie als „zu hoch“ quittiert, wissen wir, dass wir nur noch die untere Hälfte, nämlich die Zahlen von 1 bis 499, absuchen müssen. Ist 500 aber „zu tief“ so nehmen wir uns nun die Zahlen von 501 bis 1000 vor. In der Zahlmenge, in der wir nun landen, gehen wir abermals in die Mitte, und Alice wird abermals mit „zu hoch“ oder „zu tief“ antworten, ausser, wir hätten die richtige Zahl schon getroffen. Auf diese Weise fahren wir fort, gehen also stets in die Mitte des aktuellen Suchraums, der somit ständig halbiert wird – wie in der Abbildung gezeigt.

Nehmen wir an, Alice hat sich die Zahl 315 gemerkt. Unser Vorschlag „500“ würde dann mit „zu hoch“ quittiert. Darum bringen wir als zweites die Zahl 250 ins Spiel, die dann aber „zu tief“ ist. Darum gehen wir drittens in die Mitte von 250 und 500, also zur Zahl 375, die Alice aber mit „zu hoch“ zurückweist. So fortfahrend finden wir die Zahl im zehnten Schritt. Nur zehn Schritte, das ist wirklich schnell. Dieses Verfahren wird in der Praxis häufig verwendet, weil es gestattet, den Suchraum sehr schnell abzusuchen. Gebe ich beispielsweise in einem elektronischen Telefonbuch den Nachnamen „Knuth“ ein, so muss die wahrscheinlich aus Millionen von Personen bestehende nummerierte Liste so schnell wie möglich nach dem Schlüssel „Knuth“ durchsucht werden, um die Positionen von Menschen mit diesem Namen zu finden. Und das geht binär eben besonders schnell.

Wie schnell genau? Wie viele Fragen werden in unserem Spiel mit Alice sicherlich immer ausreichen? Dazu müssen wir überlegen, wie oft man die Liste halbieren kann, bis man bei einer einzigen Zahl anlangt. Eine Liste der Länge 2 kann man einmal halbieren, eine Liste der Länge 4 zweimal, eine Liste der Länge 8 dreimal, eine Liste der Länge 16 viermal, und so fort, eine Liste der Länge 1024 zehnmal. Zehn Fragen reichen bei Alice also ganz sicher immer aus. Ist umgekehrt die Listenlänge N gegeben, so liefert der Zweier-Logarithmus von N gerade die maximale Anzahl von Suchschritten.

Da wir hier schon Zahlen suchen: Können Sie alle positiven und ganzzahligen Lösungen der Gleichung x³ – y³ = 721 finden?

Armin P. Barth ist Gymnasiallehrer an der Kantonsschule Baden und Autor. Die Lösung erscheint am nächsten Dienstag auf der Seite Leben&Wissen.