Hauptinhalt
Implementierung der binären Suche eines Arrays
Nun wollen wir ansehen, wie sich die binäre Suche in einem sortierten Array verhält. Gut, JavaScript bietet bereits Methoden zur Bestimmung, ob ein bestimmtes Element ein Array ist und, wenn ja, wo es sich befindet (wie andere Programmiersprachen auch). Aber wir werden sie selbst implementieren, um zu verstehen, wie man solche Methoden implementieren kann. Hier ist ein geordnetes JS-Array der ersten 25 Primzahlen:
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
Wir wollen also wissen, ob die Zahl 67 eine Primzahl ist. Wenn sich 67 im Array befindet, ist sie eine Primzahl.
Wir möchten auch herausfinden, wie viele Primzahlen es gibt, die niedriger als 67 sind. Wenn wir die Position der Zahl 67 im Array finden, können wir damit herausfinden, wie viele niedrigere Primzahlen es gibt.
Die Position eines Elements in einem Array nennt man Index. Array-Indizes beginnen bei 0 und werden hochgezählt. Wenn ein Element den Index 0 hat, ist es das erste Element im Array. Wenn ein Element den Index 3 hat, dann gibt es 3 Elemente, die vor ihm im Array kommen.
Wenn wir das untenstehende Beispiel betrachten, können wir das Array von Primzahlen von links nach rechts Element für Element lesen, bis wir die Zahl 67 (im pinkfarbenen Kasten) finden und feststellen, dass es den Array-Index 18 hat. Die Zahlen in dieser Reihenfolge durchzusehen, nennt man lineare Suche.
Wenn wir nun erst einmal wissen, dass sich die Primzahl 67 bei Index 18 befindet, können wir sie als Primzahl identifizieren. Wir können ebenfalls schnell identifizieren, dass es 18 Elemente gibt, die vor 67 im Array kommen, also dass es 18 Primzahlen kleiner als 67 gibt.
Hast du gesehen, wie viele Schritte das dauert? Eine binäre Suche könnte effizienter sein. Da das Array
primes
25 Zahlen enthält, reichen die Indizes im Array von 0 bis 24. Mit der Schritt-für-Schritt-Anleitung aus dem vorherigen Artikel beginnen wir damit, dass min = 0
und max = 24
ist. Die erste Vermutung bei der binären Suche würde also bei Index 12 liegen (das ist (0 + 24) / 2). Ist primes[12]
gleich 67? Nein, primes[12]
ist 41.Ist der Index, den wir suchen, höher oder niedriger als 12? Da die Werte im Array aufsteigend sortiert sind, und 41 < 67 ist, sollte der Wert 67 rechts vom Index 12 sein. Anders gesagt sollte der Index, den wir versuchen zu raten, größer als 12 sein. Wir aktualisieren den Wert von
min
auf 12 + 1, oder 12, und lassen max
unverändert bei 24.Was ist der nächste zu ratende Index? Der Durchschnitt von 13 + 24 ist 18,5, was wir auf 18 abrunden, weil ein Index in einem Array eine ganze Zahl sein muss. Wir ermitteln, dass
primes[18]
gleich 67 ist.Der binäre Suchalgorithmus hört hier auf, weil er die Antwort gefunden hat. Er musste nur zwei Mal raten, anstatt 19 Mal wie bei einer linearen Suche. Du kannst dir die Schritte im Beispiel unten noch mal ansehen.
Pseudocode
Wir haben den binären Suchalgorithmus gerade in Deutsch beschrieben und ein Beispiel besprochen. Dies ist eine Umsetzungsmöglichkeit, aber die Qualität einer Erklärung in menschlicher Sprache kann sehr unterschiedlich sein. Sie kann zu kurz oder zu lang, aber vor allem zu unpräzise sein. Wir könnten dir nun direkt die binäre Suche in einer Programmiersprache wie JS oder Python erklären. Aufgrund der Anforderungen der Programmiersprache, oder weil Programme mit Fehlern umgehen müssen, die durch falsche Daten, Benutzerfehler oder Systemfehler verursacht werden, enthalten Programme aber sehr viele Details. Diese machen es schwerer, den zugrunde liegenden Algorithmus nur vom Lesen des Codes zu verstehen. Deswegen beschreiben wir Algorithmen lieber durch sogenannten Pseudocode, bei dem Englisch, oder Deutsch, mit Bestandteilen von Programmiersprachen gemischt wird.
Es folgt der Pseudocode für die binäre Suche, die mit einem Array funktioniert. Die Eingänge sind das Array, das nennen wir
array
; die Anzahl n
der Elemente in array
; und target
, die Zahl, die gesucht wird. Die Ausgabe ist der Index von target
in array
:- Setze
min = 0
undmax = n-1
. - Berechne
guess
als den Durchschnitt vonmax
undmin
, abgerundet, (so dass es eine ganze Zahl ist). - Wenn
array[guess]
gleichtarget
ist, dann stoppe. Du hast es gefunden! Gebeguess
zurück. - Wenn die Schätzung zu niedrig war, d. h.
array[guess] < target
, dann setzemin = guess + 1
. - Ansonsten war die Schätzung zu hoch. Setze
max = guess - 1
. - Gehe zurück zu Schritt 2.
Pseudocode implementieren
Abhängig von der Situation wechseln wir in diesen Tutorials zwischen Deutsch, Pseudocode und JS. Als Programmierer solltest du lernen, Pseudocode zu verstehen, und dazu fähig sein, ihn in deiner gewählten Sprache umzusetzen. Das heißt, selbst wenn wir hier JS verwenden, sollte es für dich kein Problem sein, Pseudocode in anderen Sprachen zu implementieren.
Wie würden wir Pseudocode in ein JS-Programm umwandeln? Wir sollten eine Funktion erstellen, da wir Code schreiben, der einen Eingabewert annimmt und einen Ausgabewert zurückgibt, und wir wollen, dass dieser Code für unterschiedliche Eingabewerte verwendbar ist. Die Parameter zu der Funktion, nennen wir sie
binarySearch
, werden das Array und der Zielwert sein, und der Ausgabewert der Funktion der Index des Ortes, an dem der Zielwert gefunden wurde.Jetzt gehen wir zum Rumpf der Funktion und entscheiden, wie wir ihn implementieren. Schritt 6 sagt, geh zurück zu Schritt 2. Das klingt nach einer Schleife. Sollte es eine for-Schleife oder eine while-Schleife sein? Wenn du wirklich eine for-Schleife verwenden wolltest, könntest du das zwar tun, aber die Indizes, die bei der binären Suche geraten werden, passen nicht in die sequentielle Abfolge, die eine for-Schleife so praktisch machen. Erst raten wir den Index 12 und dann 18, basierend auf einigen Berechnungen. Daher ist eine while-Schleife die bessere Wahl.
Ein wichtiger Schritt fehlt noch in diesem Pseudocode, der beim Ratespiel keine Rolle gespielt hat, aber für die binäre Suche in einem Array benötigt wird. Was soll passieren, wenn die Zahl, nach der du suchst, nicht im Array liegt? Wir legen dafür zuerst fest, welchen Index die Funktion
binarySearch
in diesem Fall zurückgeben soll. Es sollte sich um eine Zahl handeln, die kein gültiger Index des Arrays sein kann. Wir verwenden -1
, weil diese kein gültiger Index eines Arrays sein kann. (Du könntest im Prinzip jede negative Zahl verwenden.)Die Zahl ist nicht im Array enthalten, wenn es keine weiteren Ratemöglichkeiten mehr gibt. Ein Beispiel: Nehmen wir an, dass wir auf der Suche nach der Zahl 10 im Array
primes
sind. Gäbe es die 10 dort, dann läge sie zwischen den Werten 7 und 11, die die Indizes 3 und 4 haben. Wenn Du die Index-Werte für min
und max
verfolgst, so wie es die binarySearch
Funktion macht, so wirst Du feststellen, dass wir irgendwann an den Punkt gelangen, wo min
gleich 3 und max
gleich 4 sind. Die Vermutung ist dann Index 3 (denn (3 + 4) / 2 entspricht 3,5, und wird abgerundet), und primes[3]
ist weniger als 10, so dass min
zu 4\ wird. Wenn min
und max
beide den Wert 4 haben, muss die Vermutung sein, dass Index 4 ist. primes[4]
ist jedoch größer als 10. Also wird max
auf 3 gesetzt. Was bedeutet es wenn min
gleich 4 und max
gleich 3 sind? Es bedeutet, dass die einzigen möglichen Vermutungen mindestens 4 und höchstens 3\ sind. Es gibt aber keine solchen Zahlen! An dieser Stelle können wir feststellen, dass die Zahl 10 nicht im Array primes
enthalten ist, und die Funktion binarySearch
würde -1
zurückgeben. Man kann also prinzipiell feststellen, dass eine Zahl nicht in einem sortierten Array enthalten ist sobald max
kleiner als min
wird. Hier ist der modifizierte Pseudocode für binäre Suche, der den Fall behandelt, in dem die Zielnummer nicht vorhanden ist:- Setze
min = 0
undmax = n-1
. - Wenn
max < min
, dann beende:target
ist imarray
nicht enthalten. Gebe-1
zurück. - Berechne
guess
als den Durchschnitt vonmax
undmin
, abgerundet, (so dass es eine ganze Zahl ist). - Wenn
array[guess]
gleichtarget
ist, dann stoppe. Du hast es gefunden! Gebeguess
zurück. - Wenn die Schätzung zu niedrig war, d. h.
array[guess] < target
, dann setzemin = guess + 1
. - Ansonsten war die Schätzung zu hoch. Setze
max = guess - 1
. - Gehe zurück zu Schritt 2.
Nun da wir den Pseudocode zusammen durchdacht haben, wirst du selbst versuchen, die binäre Suche zu implementieren. Es ist OK, sich den Pseudocode noch mal anzuschauen - es ist sogar gut, weil du dadurch lernst, Pseudocode in ein Programm umzuwandeln.
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.
Willst du an der Diskussion teilnehmen?
- Nur zur Info falls jemand auf das gleiche Problem beim Nachprogrammieren stößt:
Der Algorithmus funnktioniert leider nicht wenn die gesuchte Zahl größer ist als die größte Zahl im Array oder kleiner ist als die kleinste Zahl im Array. Um das zu lösen müsste man noch prüfen ob guess kleiner ist als 0 oder guess größer ist als der letzte Index im Array.(1 Bewertung) - The first sentence has a subtle translation error:
"Gut, JavaScript bietet bereits Methoden zur Bestimmung, ob ein bestimmtes Element ein Array ist und, wenn ja, wo es sich befindet (wie andere Programmiersprachen auch)."
Should say "if there is a element in an array", right?
Right now it says "if an element is an array".
It should be changed to
"ob ein bestimmtes Element in einem Array ist"(1 Bewertung) - Was ist eine for-Schleife und was ist eine while-Schleife?(0 Bewertungen)
- Ich nehme an das sind Bestandteile der JS Sprache.(1 Bewertung)