If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

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:
  1. Setze min = 0 und max = n-1.
  2. Berechne guess als den Durchschnitt von max und min, abgerundet, (so dass es eine ganze Zahl ist).
  3. Wenn array[guess] gleich target ist, dann stoppe. Du hast es gefunden! Gebe guess zurück.
  4. Wenn die Schätzung zu niedrig war, d. h. array[guess] < target, dann setze min = guess + 1.
  5. Ansonsten war die Schätzung zu hoch. Setze max = guess - 1.
  6. 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 binarySearchFunktion 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:
  1. Setze min = 0 und max = n-1.
  2. Wenn max < min, dann beende: target ist im array nicht enthalten. Gebe -1 zurück.
  3. Berechne guess als den Durchschnitt von max und min, abgerundet, (so dass es eine ganze Zahl ist).
  4. Wenn array[guess] gleich target ist, dann stoppe. Du hast es gefunden! Gebe guess zurück.
  5. Wenn die Schätzung zu niedrig war, d. h. array[guess] < target, dann setze min = guess + 1.
  6. Ansonsten war die Schätzung zu hoch. Setze max = guess - 1.
  7. 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?

  • leaf green style-Avatar für Benutzer Man Fred
    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)
    Default Khan Academy avatar-Avatar für Benutzer
  • leafers seed style-Avatar für Benutzer Con Stantin
    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)
    Default Khan Academy avatar-Avatar für Benutzer
  • leafers seed style-Avatar für Benutzer dein Popo
    Was ist eine for-Schleife und was ist eine while-Schleife?
    (0 Bewertungen)
    Default Khan Academy avatar-Avatar für Benutzer
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.