Binärsuche

Die binäre Suche ist ein effizienter Algorithmus, mit dem ein Objekt in einer sortierten Liste von Objekten gefunden werden kann. Er funktioniert so, dass der Teil der Liste, in dem sich das Objekt befinden könnte, immer wieder halbiert wird, bis der potentielle Aufenthaltsort auf einen eingeschränkt wurde. Wir haben die binäre Suche im Ratespiel im Einführungstutorial verwendet.

Eine der gebräuchlichsten Arten der Verwendung von Binärsuche ist es, ein Objekt in einem Array zu suchen. Zum Beispiel enthält der Sternenkatalog Tycho-2 Informationen über die hellsten 2.539.913 Sterne in unserer Galaxie. Nehmen wir an, dass du im Katalog, basierend auf dem Namen des Sterns, nach einem bestimmten Stern suchen willst. Wenn das Programm jeden Stern, beginnend mit dem ersten, im Sternenkatalog der Reihenfolge nach untersuchen würde (diesen Algorithmus nennt man lineare Suche), muss der Computer eventuell im schlimmsten Fall alle 2.539.913 Sterne prüfen, um den gesuchten Stern zu finden. Wenn der Katalog alphabethisch nach Sternennamen sortiert wäre, würde man mit der binären Suche sogar im schlimmsten Fall nicht mehr als 22 Sterne untersuchen müssen.

In den nächsten paar Kapiteln erklären wir, wie die Algorithmen in JavaScript implementiert werden und wie ihre Effizient analysiert werden kann.

Wenn wir einem Mitmenschen einen Algorithmus beschreiben, reicht häufig eine unvollständige Beschreibung aus. Bei einem Rezept für einen Kuchen können einige Details ausgelassen werden, da das Rezept davon ausgeht, dass du weißt, wie man den Kühlschrank öffnet um die Eier herauszuholen und wie man sie aufschlägt. Menschen wissen vielleicht intuitiv, wie man die fehlenden Details ergänzt, nicht aber Computerprogramme. Aus diesem Grund müssen wir Computeralgorithmen komplett beschreiben.

Um einen Algorithmus in einer Programmiersprache zu implementieren, musst du ihn bis ins Detail verstehen. Was sind die Eingabewerte für die Problemlösung? Was die Ausgabewerte? Welche Variablen sollten angelegt werden, und welche initialen Werte sollten diese haben? Welche anfänglichen Schritte sollten unternommen werden, um andere Werte und letztendliche die Ausgabewerte zu berechnen? Werden bei diesen Schritten Anweisungen wiederholt, so dass sie mit einer Schleife vereinfacht werden können?

Schauen wir uns mal an, wie man die binäre Suche genau beschreiben kann. Die Hauptidee bei der binären Suche ist es, den aktuellen Bereich zu verfolgen, in dem es vernünftig ist, weiterzuraten. Beispielsweise denke ich mir eine Zahl zwischen Eins und 100 aus, wie beim Ratespiel. Wenn du schon 25 geraten hast und ich dir gesagt habe, dass meine Zahl höher ist, und auch schon 81 geraten hast, und ich dir gesagt habe, dass meine Zahl niedriger ist, dann ist es vernünftig, nur im Bereich zwischen 26 und 80 weiterzuraten. Der rote Bereich des Zahlenstrahls hier enthält die Werte, die weiterhin möglich sind, und der schwarze Bereich die Werte, die wir schon ausgeschlossen haben.

Mit jeder Zahl, die geraten wird, wird dieser Bereich mit möglichen Werten in zwei ungefähr gleich große Bereiche geteilt. Wenn dein geratener Wert nicht richtig ist, sage ich dir, ob er zu hoch oder zu niedrig ist, und du kannst ungefähr die Hälfte der möglichen Werte ausschließen. Wenn zum Beispiel der aktuelle Bereich an möglichen Werten 26 bis 80 ist, würdest du den Wert in der Mitte raten: $(26+80)/2$‍, oder 53. Wenn ich dir sage, dass 53 zu hoch ist, kannst du alle Zahlen von 53 bis 80 ausschließen, womit der Bereich halbiert wird und 26 bis 52 als neuer Bereich an möglichen Werten übrigbleibt.

Für das Ratespiel können wir mithilfe von ein paar Variablen diesen Bereich der möglichen Werte verfolgen. Sagen wir, dass für diese Runde die Variable $min$‍ der minimale aktuell mögliche Ratewert ist und die Variable $max$‍ der minimale aktuell mögliche Ratewert. Der Eingabewert für die Aufgabe ist die Zahl $n$‍, die höchste mögliche Nummer, die sich dein Mitspieler ausdenken kann. Wir nehmen an, dass die niedrigste mögliche Zahl Eins ist, aber es wäre einfach, den Algorithmus so zu ändern, dass die niedrigste mögliche Zahl als zweiter Eingabewert verwendet wird.

Hier ist eine Beschreibung Schritt-für-Schritt der binären Suche:

Wir könnten diese Beschreibung noch genauer machen, indem wir genau die Eingabe- und Ausgabewerte für den Algorithmus beschreiben und klären, was wir mit Anweisungen wie "schätze eine Zahl" und "hör auf" meinen. Aber für's erste ist es genug.

Als nächstes werden wir sehen, wie wir die binäre Suche auf ein Array anwenden können und besprechen, wie man Beschreibungen von Algorithmen in funktionierenden Code umwandelt.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.