Binäre Suche Javascript

Michael Zippo 04.11.2021

So codieren Sie eine binäre Suche in JavaScript

Suchalgorithmen erleichtern das Leben eines Programmierers erheblich. Dies erleichtert das Auffinden eines bestimmten Elements in einem Datensatz mit Dutzenden, Hunderten oder Tausenden von Elementen.

Eine der beliebtesten Suchformen ist die binäre Suche. Diese Suche findet schnell ein Element in einem Array. Jedes Mal, wenn die Suche ein Element untersucht, wird die Anzahl der zu findenden Elemente halbiert.

In diesem Leitfaden sprechen wir darüber, was binäre Suchen sind und wie sie funktionieren. Als Nächstes fahren wir mit der Implementierung einer binären Suche mit zwei verschiedenen Ansätzen fort: iterativ und rekursiv.

Lassen Sie uns einen binären Suchalgorithmus in !

Was ist eine binäre Suche ?

Eine binäre Suche ist ein Computeralgorithmus, der nach einem Element in einem geordneten Array sucht.

Beginnen Sie in der Mitte eines Arrays und prüfen Sie, ob das mittlere Element kleiner, gleich oder größer als die gesuchte Zahl ist.

Ist die Zahl kleiner, der Algorithmus weiß, wie man weiter in der linken Hälfte des Arrays sucht, wo die kleineren Zahlen sind ; Wenn die Zahl größer ist, konzentriert sich der Algorithmus auf die rechte Hälfte des Arrays. Binäre Suchen funktionieren nur auf geordneten Listen.

Binäre Suchen sind effizienter als lineare Suchen. Tatsächlich wird jedes Mal, wenn eine Suche durchgeführt wird, die Anzahl der noch zu findenden Elemente in der Liste um die Hälfte reduziert.

So verwenden Sie eine binäre Suche

Eine binäre Suche ist einfach zu verstehen, sobald Sie sie gelernt haben.

Bevor Sie einen binären Suchalgorithmus implementieren, lassen Sie uns einen Rückblick wagen. Wir finden die Nummer " 9 " in einer Liste. Beginnen wir mit einer geordneten Liste:

6 < / td>

Zuerst müssen wir die mittlere Zahl finden und einer Variablen zuweisen. Dies wird ermittelt, indem die Summe der ersten und der letzten Zahl berechnet und durch zwei geteilt wird. Wir nennen diese "zentrale" Variable:

Start	< br>	Mittel		Ende
2	6	8	9	10

8 ist unsere Durchschnittszahl. So können wir die zentrale Zahl mit der gesuchten vergleichen. Wenn die zentrale Zahl mit der gesuchten identisch ist, kann unsere Suche anhalten.

In diesem Beispiel ist 8 nicht gleich 9. Unsere Suche geht weiter.

Also müssen wir vergleichen, ob die Zahl in der Mitte größer als 9 ist. Das ist es nicht.

Das sagt uns, dass die Zahl, nach der wir suchen, nach der Mitte liegen muss Zahl. 9 ist größer als 8 in einer geordneten Liste. Setze unsere Startzahl gleich der Zentralzahl. Denn wir wissen, dass die gesuchte Zahl nicht vor der Zentralzahl steht.

Wenn die Zahl, nach der wir suchen, mehr Baby ist, setzen wir die letzte Zahl auf die mittlere Zahl. Da die Zahl kleiner als die mittlere Zahl ist, könnten wir unsere Suche auf die untere Hälfte der Liste konzentrieren.

Die binäre Suche wird in der oberen Hälfte der Liste erneut wiederholt, da 9 größer als 8 ist:

< td> Mittel

Start Ende

8 < /td>

Lassen Sie uns die zentrale Nummer finden. Das ist 9. Wir können 9 mit der gesuchten Zahl vergleichen. 9 entspricht der Zahl, nach der wir suchen.

Das bedeutet, dass unsere Forschung aufhören kann. Wir haben Platz 9 auf unserer Liste gefunden!

So implementieren Sie eine binäre Suche in JavaScript

Binäre Suchen können mit einem iterativen oder rekursiven Ansatz implementiert werden.

Iterative binäre Suche

Eine iterative binäre Suche verwendet eine While-Schleife, um ein Element in einer Liste zu finden. Diese Schleife läuft, bis das Element in der Liste gefunden wird oder bis die Liste durchsucht wurde.

Beginnen wir mit dem Schreiben einer Funktion , die unsere binäre Suche durchführt:

Beginnen wir mit der Definition von zwei Variablen: start und end. Diese verfolgen die höchsten und niedrigsten Werte, mit denen unsere Forschung arbeitet. Wir verwenden eine While-Schleife , die ausgeführt wird, bis die Startnummer größer als die Endnummer ist. Diese Schleife berechnet die Zwischenzahl zwischen dem Anfang und dem Ende der Liste.

Wenn die Zahl, nach der wir suchen, gleich der Zahl in der Mitte ist, wird die Zahl in der Mitte an unser Hauptprogramm zurückgegeben Ist die Zahl kleiner, wird der Seed-Wert auf die mittlere Zahl plus 1 gesetzt. Diese Vergleiche werden mithilfe einer if-Anweisung durchgeführt.

Andernfalls wird die letzte Zahl auf die mittlere Zahl minus eins gesetzt. Wenn unsere Zahl nach dem Ausführen der While-Schleife nicht gefunden wird, gibt sie -1 zurück. Wir nennen das die Grundbedingung. In unserem Hauptprogramm wir prüfen, ob die zurückgegebene Zahl gleich -1 ist, das bedeutet, dass unsere Zahl nicht gefunden wurde.

Unsere Funktion funktioniert noch nicht. Wir müssen ein Hauptprogramm schreiben, um es zu benennen:

Wir haben eine Liste von Nummern definiert, nach denen gesucht werden soll, und die Nummer, die wir in unserer Liste finden möchten. Als Nächstes haben wir die Funktion binarySearch aufgerufen. Dies wird unsere Forschung erledigen. Die Suche gibt -1 oder die Position des gesuchten Elements zurück.

-1 zeigt an, dass ein Element nicht gefunden werden konnte. Wenn ein Element nicht gefunden wird, wird der Inhalt unserer else -Anweisung ausgeführt. Andernfalls wird der Inhalt der if -Anweisung ausgeführt.

Lassen Sie uns unseren Code ausführen:

Dies sagt uns, dass unsere Suche erfolgreich war!

Rekursive binäre Suche

Eine rekursive binäre Suche gilt als eleganter als eine iterative Suche. Dies liegt daran, dass binäre Suchen immer wieder dieselbe Operation für eine Liste ausführen. Dieses Verhalten kann mithilfe eines Rekursionsalgorithmus implementiert werden.

Öffnen Sie eine neue JavaScript-Datei und fügen Sie diesen Code ein:

Dieser Code führt dieselben Vergleiche durch wie unsere erste Suche. Überprüfen Sie, ob die mittlere Zahl gleich, größer oder kleiner als die gesuchte Zahl ist.

Zu Beginn unseres function haben wir eine if-Anweisung verwendet, um zu überprüfen, ob die Startnummer größer als die Endnummer ist. Wenn dies der Fall ist, bedeutet dies, dass unser Element nicht in der von uns angegebenen Liste gefunden wurde. In diesem Fall geben wir -1 an das Hauptprogramm zurück.

Wenn die gesuchte Nummer mit der zentralen Nummer identisch ist, wird die zentrale Nummer an das Hauptprogramm zurückgegeben die gesuchte Zahl größer oder kleiner als die zentrale Zahl ist, wird unsere binäre Suchfunktion erneut ausgeführt, bis unser Element gefunden ist.

Um diese Funktion auszuführen, müssen wir eine Änderung an unserem Hauptprogramm vornehmen:

Wir müssen zwei weitere Parameter übergeben: die Werte ‚Äã‚Äão von "start" und "end". Der Wert von „start“ ist gleich 0. Der Wert von „end“ ist gleich der Länge der Liste minus eins.

Lassen Sie uns unseren Code ausführen und sehen, was passiert:

Unsere binäre Suche war erfolgreich! Es verwendet denselben zugrunde liegenden Algorithmus wie der iterative Ansatz. Der Unterschied besteht darin, dass die binäre Suche mithilfe einer Funktion ausgeführt wird, die aufgerufen wird, bis das Element gefunden wird oder bis die Suche in der Liste abgeschlossen ist, je nachdem, was zuerst eintritt.

Fazit

Binäre Suchen erleichtern das Auffinden eines Elements in einer Liste. Jedes Mal, wenn eine Suche durchgeführt wird, wird die Anzahl der noch zu findenden Elemente in einer Liste um die Hälfte reduziert. Dadurch wird eine binäre Suche effizienter als eine lineare Suche.

Jetzt können Sie es tun implementieren Sie die binäre Suche in JavaScript wie ein Experte!