Binärer Suchalgorithmus mit BEISPIEL

Bevor wir die binäre Suche lernen, lernen wir Folgendes:

Was ist Suche?

Die Suche ist ein Dienstprogramm, das es dem Benutzer ermöglicht, Dokumente, Dateien, Medien oder andere Arten von Daten zu finden, die in einer Datenbank gespeichert sind. Die Suche basiert auf dem einfachen Prinzip, die Kriterien mit den Datensätzen abzugleichen und sie dem Benutzer anzuzeigen. Auf diese Weise funktioniert die einfachste Suchfunktion.

Was ist binäre Suche?

Eine binäre Suche ist ein erweiterter Suchalgorithmus, der Daten aus einer sortierten Liste von Elementen findet und abruft. Sein grundlegendes Funktionsprinzip besteht darin, die Daten in der Liste in zwei Hälften zu teilen, bis der gewünschte Wert gefunden und dem Benutzer im Suchergebnis angezeigt wird. Die binäre Suche ist allgemein bekannt als Halbintervallsuche oder einen logarithmische Suche.

Wie funktioniert die binäre Suche?

Die binäre Suche funktioniert folgendermaßen:

• Der Suchvorgang beginnt mit der Suche nach dem mittleren Element des sortierten Datenarrays
• Anschließend wird der Schlüsselwert mit dem Element verglichen
• Wenn der Schlüsselwert kleiner als das mittlere Element ist, werden bei der Suche die oberen Werte bis zum mittleren Element analysiert, um sie zu vergleichen und abzugleichen
• Falls der Schlüsselwert größer als das mittlere Element ist, analysiert die Suche die niedrigeren Werte des mittleren Elements zum Vergleich und zur Übereinstimmung

Beispiel für eine binäre Suche

Betrachten wir das Beispiel eines Wörterbuchs. Wenn Sie ein bestimmtes Wort finden müssen, geht niemand jedes Wort der Reihe nach durch, sondern sucht nach dem Zufallsprinzip die nächstgelegenen Wörter, um nach dem erforderlichen Wort zu suchen.

Das obige Bild veranschaulicht Folgendes:

1. Sie haben ein Array mit 10 Ziffern und das Element 59 muss gefunden werden.
2. Alle Elemente werden mit dem Index von 0 – 9 gekennzeichnet. Nun wird die Mitte des Arrays berechnet. Dazu nehmen Sie die Werte ganz links und rechts des Index und dividieren sie durch 2. Das Ergebnis ist 4.5, aber wir nehmen den Mindestwert. Daher ist die Mitte 4.
3. Der Algorithmus verwirft alle Elemente von der Mitte (4) bis zur niedrigsten Grenze, da 59 größer als 24 ist und das Array jetzt nur noch 5 Elemente enthält.
4. Nun ist 59 größer als 45 und kleiner als 63. Die Mitte ist 7. Daher wird der rechte Indexwert zu Mitte – 1, was 6 entspricht, und der linke Indexwert bleibt derselbe wie zuvor, also 5.
5. An diesem Punkt wissen Sie, dass 59 nach 45 kommt. Daher wird der linke Index, der 5 ist, ebenfalls zur Mitte.
6. Diese Iterationen werden fortgesetzt, bis das Array auf nur noch ein Element reduziert ist oder das zu findende Element in die Mitte des Arrays gelangt.

Beispiel 2

Schauen wir uns das folgende Beispiel an, um die Funktionsweise der binären Suche zu verstehen

1. Sie haben ein Array mit sortierten Werten im Bereich von 2 bis 20 und müssen 18 finden.
2. Der Durchschnitt der unteren und oberen Grenzen beträgt (l + r) / 2 = 4. Der gesuchte Wert ist größer als der Mittelwert, der 4 beträgt.
3. Die Array-Werte, die kleiner als der Mittelwert sind, werden aus der Suche entfernt und nach Werten gesucht, die größer als der Mittelwert 4 sind.
4. Dabei handelt es sich um einen wiederkehrenden Teilungsvorgang, bis der eigentliche Suchgegenstand gefunden ist.

Warum brauchen wir eine binäre Suche?

Die binäre Suche ist aus folgenden Gründen die bessere Wahl als Suchalgorithmus:

• Die binäre Suche funktioniert effizient bei sortierten Daten, unabhängig von der Datengröße
• Anstatt die Suche durch Durchsuchen der Daten in einer Reihenfolge durchzuführen, greift der binäre Algorithmus zufällig auf die Daten zu, um das erforderliche Element zu finden. Dadurch werden die Suchzyklen kürzer und genauer.
• Bei der binären Suche werden Vergleiche der sortierten Daten nach einem Ordnungsprinzip durchgeführt, statt Gleichheitsvergleiche zu verwenden, die langsamer und meist ungenau sind.
• Nach jedem Suchzyklus teilt der Algorithmus die Größe des Arrays in die Hälfte, sodass er in der nächsten Iteration nur in der verbleibenden Hälfte des Arrays funktioniert

Lernen Sie unser nächstes Tutorial von Lineare Suche: Python, C++ Beispiel

Zusammenfassung

• Search ist ein Dienstprogramm, mit dem Benutzer nach Dokumenten, Dateien und anderen Datentypen suchen können. Eine binäre Suche ist ein erweiterter Suchalgorithmus, der Daten aus einer sortierten Liste von Elementen findet und abruft.
• Die binäre Suche wird allgemein als Halbintervallsuche oder logarithmische Suche bezeichnet
• Es funktioniert, indem das Array bei jeder Iteration, unter der das erforderliche Element gefunden wird, in zwei Hälften geteilt wird.
• Die binärer Algorithmus Nimmt die Mitte des Arrays, indem es die Summe der linken und rechten Indexwerte durch 2 dividiert. Jetzt löscht der Algorithmus entweder die untere oder obere Grenze der Elemente aus der Mitte des Arrays, je nachdem, welches Element gefunden werden soll.
• Der Algorithmus greift zufällig auf die Daten zu, um das erforderliche Element zu finden. Dadurch werden die Suchzyklen kürzer und genauer.
• Bei der binären Suche werden Vergleiche der sortierten Daten nach einem Ordnungsprinzip durchgeführt, anstatt Gleichheitsvergleiche zu verwenden, die langsam und ungenau sind.
• Für unsortierte Daten ist eine binäre Suche nicht geeignet.