Die binäre Suche ist ein effizienter Algorithmus, um ein Element in einem sortierten Array zu finden. Es ist ein beliebter Ansatz, der in der Informatik verwendet wird, um schnell nach den benötigten Informationen zu suchen. Die binäre Suche basiert auf dem Prinzip, das sortierte Array in zwei Hälften zu teilen und den Wert des mittleren Elements anschließend mit dem Zielwert zu vergleichen.
Die Zeitkomplexität der binären Suche beträgt O(log n), was sie wesentlich schneller macht als eine einfache lineare Suche. Mit diesem Algorithmus können Entwickler und Ingenieure Informationen in großen Datenmengen schnell finden. In einigen Fällen kann die binäre Suche so effektiv sein, dass Sie Milliarden von Elementen in einer beobachteten Zeit bearbeiten können.
Um die binäre Suche effektiv zu nutzen, ist es jedoch zwingend erforderlich, das Array zu sortieren. Daher müssen Sie vor der Anwendung des Algorithmus sicherstellen, dass die Daten in der richtigen Reihenfolge angeordnet sind. Die binäre Suche setzt auch voraus, dass das Array in aufsteigender oder absteigender Reihenfolge angeordnet ist, anstatt doppelte Elemente zu enthalten. Andernfalls ist das Ergebnis des Algorithmus möglicherweise nicht korrekt.
Was ist eine binäre Suche?
Die binäre Suche hat eine Laufzeit von O(log n), wobei n die Größe des Arrays ist. Aus diesem Grund wird der Algorithmus häufig verwendet, um große Datenmengen zu durchsuchen. Es kann auch auf verschiedene Datenstrukturen angewendet werden, einschließlich Listen und Bäume, wenn die darin enthaltenen Daten sortiert sind.
Das Prinzip der binären Suche basiert auf der Aufteilung des Arrays in zwei Hälften und dem Vergleich des gewünschten Werts mit dem Mittelelement. Wenn die Werte übereinstimmen, wird die Suche beendet. Wenn der gewünschte Wert kleiner als das Mittelelement ist, wird der Vorgang für die linke Hälfte des Arrays wiederholt. Wenn der gewünschte Wert größer als das Mittelelement ist, wird der Vorgang für die rechte Hälfte des Arrays wiederholt. Dieser Prozess wird fortgesetzt, bis der gesuchte Wert gefunden wird oder das Array vollständig validiert ist.
Sobald die binäre Suche den gewünschten Wert findet, gibt sie seinen Index im Array zurück. Wenn kein Wert gefunden wird, gibt der Algorithmus einen speziellen Wert zurück, normalerweise -1, um anzugeben, dass der Wert nicht im Array vorhanden ist.
Die binäre Suche ist einer der grundlegenden Algorithmen in der Programmierung und wird in verschiedenen Bereichen, einschließlich Datenbanksuche, wissenschaftlichem Computing und maschinellen Lernalgorithmen, weit verbreitet.
Das Prinzip der binären Suche
Das Prinzip der binären Suche ist wie folgt:
- Ein geordnetes Datenarray wird angegeben.
- Die Suchgrenzen werden definiert - die Anfangs- und Endindizes des Arrays.
- Das zentrale Element des Arrays befindet sich.
- Das gesuchte Element wird mit dem zentralen Element verglichen:
- Wenn das gesuchte Element gleich dem Mittelpunkt ist, wird die Suche abgeschlossen – das Element wurde gefunden.
- Wenn das gesuchte Element kleiner als das zentrale Element ist, wird die Suche in der linken Hälfte des Arrays fortgesetzt, andernfalls in der rechten Hälfte.
- Die Suchgrenzen werden entsprechend dem Vergleichsergebnis verengt:
- Wenn das gesuchte Element kleiner als das Mittelelement ist, verschiebt sich die obere Grenze um die Mittelposition minus eins, andernfalls wird die untere Grenze um die Mittelposition plus eins verschoben.
- Der Vorgang wird wiederholt, bis das gesuchte Element gefunden wird oder die Suchgrenzen übereinstimmen.
Die binäre Suche ist ideal für die Arbeit mit großen, sortierten Datenarrays, da ihre Komplexität O(log n) ist, wobei n die Größe des Arrays ist. Diese Effizienz wird dadurch erreicht, dass die Größe des Suchbereichs bei jeder Iteration der Suche ungefähr um die Hälfte reduziert wird.
Vorteile der Verwendung der binären Suche
| Vorteil | Die Beschreibung |
| Effizienz | Die binäre Suche wird hauptsächlich während der Zeit von O(log n) durchgeführt, wobei n die Größe des Arrays ist. Dies macht es deutlich schneller als eine einfache lineare Suche. |
| Vielseitigkeit | Die binäre Suche kann unabhängig von ihrem Datentyp auf jedes sortierte Array angewendet werden. Es funktioniert sowohl für numerische Werte als auch für Zeichenfolgenobjekte oder benutzerdefinierte Objekte. |
| Einfache Implementierung | Der binäre Suchalgorithmus ist relativ einfach zu implementieren und erfordert keine komplexen Datenstrukturen oder speziellen Operationen. |
| Minimale Anzahl von Vergleichen | Die binäre Suche reduziert die Anzahl der Vergleiche, sodass Sie bei jedem Schritt die Hälfte der Array-Elemente sofort ausschließen können. Dies ist besonders nützlich, wenn das Array groß ist oder die Anzahl der Operationen begrenzt ist, z. B. in eingebetteten Systemen. |
| Widerstandsfähigkeit gegen Veränderungen | Die binäre Suche hängt nicht von der Reihenfolge der Elemente im Array ab. Selbst wenn das Array in umgekehrter Reihenfolge sortiert ist, funktioniert der Algorithmus immer noch korrekt. |
All diese Vorteile machen die binäre Suche zu einem unverzichtbaren Werkzeug bei der Arbeit mit sortierten Arrays. Es ermöglicht Ihnen, die benötigten Elemente effizient und schnell zu finden und eine Reihe von Aufgaben im Zusammenhang mit der Suche und Filterung von Daten zu vereinfachen. Die Verwendung der binären Suche wird besonders in Fällen empfohlen, in denen die Leistung und Effizienz des Algorithmus eine wichtige Rolle spielen.
Wie verwende ich die binäre Suche in einem Array?
Befolgen Sie diese Schritte, um die binäre Suche in einem Array zu verwenden:
- Stellen Sie sicher, dass das Array in aufsteigender oder absteigender Reihenfolge sortiert ist.
- Legen Sie die Anfangswerte für die Variablen low und high fest - dies sind die Indizes für die Anfangs- und Endelemente des Arrays.
- Berechnen Sie die Mitte des Arrays als die Summe von low und high, geteilt in zwei Hälften.
- Vergleichen Sie den Wert des Mittelelements mit dem gewünschten Wert.
- Wenn das Mittelelement gleich dem gewünschten Wert ist, geben Sie seinen Index im Array zurück.
- Wenn das Mittelelement kleiner als der gewünschte Wert ist, aktualisieren Sie den Wert auf low, indem Sie ihm den Wert mid + 1 zuweisen.
- Wenn das Mittelelement größer ist als der gewünschte Wert, aktualisieren Sie den Wert high, indem Sie ihm den Wert mid - 1 zuweisen.
- Wiederholen Sie die Schritte 3 bis 7, bis low größer als high ist, in diesem Fall wird das Element nicht gefunden und die Suche ist abgeschlossen.
Die binäre Suche ermöglicht es Ihnen, ein Element in einem Array schneller zu finden als die lineare Suche, insbesondere bei großen Arrays. Es ist einer der wichtigsten Suchalgorithmen und wird häufig in der Programmierung verwendet, um verschiedene Probleme zu lösen.
Beispiel für die Verwendung einer binären Suche mit einem sortierten Array
Nehmen wir zum Beispiel das folgende Array von ganzen Zahlen:
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]Angenommen, wir müssen den Wert 11 in diesem Array mithilfe der binären Suche finden.
Schritte zur binären Suche:
- Setzen Sie den Anfangsindex des Arrays auf low , gleich 0, und den Endindex auf high , gleich der Länge des Arrays minus eins.
- Holen Sie sich den durchschnittlichen Index des Arrays - mid , indem Sie die Summe von low und high durch zwei dividieren.
- Vergleichen Sie den gewünschten Wert mit dem Array-Element, das sich am Index mid befindet. Wenn sie gleich sind, wird der Wert gefunden und der mid-Index wird zurückgegeben.
- Wenn der gesuchte Wert größer als das Element im Index mid ist, aktualisieren Sie den Wert von low auf mid + 1 und wiederholen Sie die Schritte 2 bis 4.
- Wenn der gesuchte Wert kleiner als das Element im Index mid ist, aktualisieren Sie den Wert von high auf mid - 1 und wiederholen Sie die Schritte 2 bis 4.
- Wenn der gesuchte Wert nicht im Array gefunden wird, wird -1 zurückgegeben.
Wenn wir diese Schritte auf unser Beispiel anwenden, erhalten wir die folgende Abfolge von Aktionen:
- low = 0, high = 9, mid = (0 + 9) / 2 = 4 . Vergleichen Sie den Wert 11 mit dem Array-Element am Index 4 (Wert 9). Der gesuchte Wert ist größer, daher aktualisieren Sie low = 5 .
- low = 5, high = 9, mid = (5 + 9) / 2 = 7 . Vergleichen Sie den Wert 11 mit dem Array-Element am Index 7 (Wert 15). Der gesuchte Wert ist kleiner, daher aktualisieren Sie high = 6 .
- low = 5, high = 6, mid = (5 + 6) / 2 = 5 . Vergleichen Sie den Wert 11 mit dem Array-Element am Index 5 (Wert 11). Der gesuchte Wert wurde gefunden, wir geben den Index 5 zurück .
Also haben wir den Wert 11 im sortierten Array gefunden und seinen Index erhalten - 5 .
Beispiel für die Verwendung einer binären Suche mit einem inkrementellen Array
Die Idee ist wie folgt: Wir beginnen mit einem kleinen Array, das ausreicht, um eine binäre Suche durchzuführen. Wenn das Element nicht gefunden wird, erhöhen wir die Größe des Arrays und wiederholen die Suche. Der Prozess wird fortgesetzt, bis das Element gefunden wird oder das Array vollständig gefüllt ist.
Betrachten Sie ein Beispiel für die Verwendung einer binären Suche mit einem inkrementellen Array. Lassen Sie uns ein geordnetes Array von ganzen Zahlen haben:
const array = [2, 3, 5, 7, 10, 12, 15, 18, 20];
Wir wollen die Position der Zahl 15 im Array finden. Um dies zu tun, verwenden wir eine binäre Suche mit einem inkrementellen Array. Beginnen wir mit einem kleinen Array der ersten beiden Elemente:
const smallArray = [2, 3];let left = 0;let right = smallArray.length - 1;while (left else if (smallArray[middle] < 15) else if (left > right && right === smallArray.length - 1) >
Ursprünglich haben wir ein Array [2, 3]. Während wir eine binäre Suche durchführen, erhöhen wir die Größe, indem wir das nächste Element aus dem ursprünglichen Array hinzufügen. In diesem Fall ist dies die Zahl 5. Dann suchen wir weiter und erhöhen das Array erneut, indem wir die Zahl 7 hinzufügen. Am Ende wird unser Array bei der Suche nach der Zahl 15 die Form haben [2, 3, 5, 7]. In der letzten Iteration wird die Suche nach der Zahl 15 erfolgreich sein und wir erhalten die Position der Zahl im Array.
Die binäre Suche mit einem inkrementellen Array ermöglicht eine effiziente Suche nach Elementen in Arrays unbekannter Größe. Es ist eines der leistungsfähigen Werkzeuge bei der Arbeit mit großen Datensätzen.
Komplexität des binären Suchalgorithmus
Wenn das mittlere Element gleich dem gesuchten Element ist, ist die Suche erfolgreich und wir geben die Position dieses Elements im Array zurück. Wenn das mittlere Element kleiner als das gesuchte Element ist, aktualisieren wir den linken Rand der Suche um die Position rechts vom mittleren Element und wiederholen den Vorgang. Wenn das mittlere Element größer ist als das gesuchte Element, aktualisieren wir den rechten Rand der Suche um die Position links vom mittleren Element und wiederholen den Vorgang.
Die Komplexität des binären Suchalgorithmus beträgt O(log n), wobei n die Größe des Arrays ist. Dies bedeutet, dass die Ausführungszeit des Algorithmus langsam ansteigt, wenn die Größe des Arrays zunimmt. Die binäre Suche ist sehr effektiv für große sortierte Arrays, da sie die Anzahl der Vergleiche reduziert, die Sie durchführen müssen, um ein Element zu finden.
Es ist auch erwähnenswert, dass der binäre Suchalgorithmus erfordert, dass das Array sortiert wird. Wenn das Array nicht sortiert ist, muss vor der Anwendung der binären Suche eine Sortierung durchgeführt werden, was zusätzliche Zeit in Anspruch nehmen kann.
Zeitliche Komplexität
Bei einer binären Suche muss das Array vorsortiert werden. Wenn das Array daher nicht sortiert ist, müssen zusätzliche Operationen durchgeführt werden, um es zu sortieren, was ebenfalls zusätzliche Zeit in Anspruch nimmt.
Die Komplexität von O(log n) ist sehr gut, besonders wenn Sie mit großen Arrays arbeiten. Die binäre Suche ermöglicht es Ihnen, ein Element in einem Array für eine relativ geringe Anzahl von Operationen zu finden, selbst wenn das Array Millionen von Elementen enthält.
Die folgende Tabelle zeigt den Vergleich der zeitlichen Komplexität der binären Suche mit anderen gängigen Suchalgorithmen:
| Algorithmus | Zeitliche Komplexität |
|---|---|
| Lineare Suche | O(n) |
| Binäre Suche | O(log n) |
| Fibonacci-Suche | O(log n) |
| Interpolationssuche | O(log log n) |
Wie aus der Tabelle hervorgeht, ist die Ausführungszeit einer binären Suche wesentlich geringer als bei einer linearen Suche und wird durch eine effizientere Reduzierung des Suchbereichs erreicht, indem das Array bei jeder Iteration in zwei Hälften geteilt wird.
