Binäre Suche

Wenn man einen Namen im Telefonbuch, ein Stichwort im Lexikon oder im Wörterbuch sucht, was macht man da? Man schlägt das Buch irgendwo auf, meistens eher in der Mitte. Dann muss man kurz nachdenken: Befindet sich der gesuchte Begriff weiter vorne oder weiter hinten von dort aus gesehen, wo man aufgeschlagen hat? Entsprechend schlägt man das Buch weiter vorne oder weiter hinten auf, aber doch eher wieder in der Mitte des Buchteils. Dies setzt man so fort, bis man glaubt, schnell auf die richtige Seite blättern zu können. Erst wenn man auf der vermeintlich richtigen Seite angekommen ist, sucht man Wort für Wort den gewünschten Eintrag.

Ein interessanter Algorithmus, nicht wahr? Er hat auch einen Namen: Binäre Suche.

Warum "binär"? Weil man immer in zwei Hälften teilt. Damit kann man mit jedem Schritt viele Seiten weglassen, die man nicht mehr zu durchsuchen braucht.

Übrigens kann man diesen Algorithmus auch dazu verwenden, aus 32 äußerlich völlig gleichen Goldmünzen die etwas leichtere (gefälschte) Münze herauszufinden. Man muss nicht immer zwei Münzen nehmen und gegeneinander abwägen. (Damit könnte man Glück haben und gleich beim ersten Mal die leichtere Münze erwischen. Aber im schlimmsten Fall benötigt man 16 Wägungen...)
Mit immer gleich vielen Wägungen, nämlich 5, kommt man zum Ergebnis, wenn man mit jeweils 16 Münzen auf jeder Wagschale beginnt. Damit kann man nach der ersten Wägung 16 Münzen ausschließen. Man setzt mit 8 Münzen auf jeder Wagschale fort. Dann mit 4. Und so weiter, bis man nach 5 Wägungen die leichtere hat.

Oder kennst du den Trick? Jemand denkt an eine Zahl, etwa zwischen 1 und 1000, und du errätst sie, indem du 10 Fragen stellst, die der andere mit Ja oder Nein beantwortet?

Beispiele

I am from Austria Binäre Suche im Österreichisch-Wörterbuch

Binäre suche in Scratch-2 errät die von dir gedachte Zahl...

Binary Search

Weiterführende Informationen

Da mit jeder Frage die Menge halbiert wird, kann man mit n Fragen einen Bereich von 2ⁿ Werten absuchen. Für einen Bereich von 1000 Werten benötigt man also 10 Fragen (weil 2¹⁰=1024).
Was macht man da eigentlich?
Angenommen, die gesuchte Zahl ist 637 (oder der gesuchte Lexikon-Eintrag befindet sich an Position 637). Die Fragen und die Antworten darauf lauten: größergleich 512? Ja // größergleich 768? Nein // größergleich 640? Nein // größergleich 576? Ja // größergleich 608? Ja // größergleich 624? Ja // größergleich 632? Ja // größergleich 636? Ja // größergleich 638? Nein // größergleich 637? Ja
Wenn man statt Ja "1" schreibt und statt Nein "0", erhält man 1001111101, den Binärcode von 637. Dies ist also zugleich ein Algorithmus zur Umwandlung einer Dezimalzahl in eine Binärzahl.