Bevor wir die binäre Suche lernen, lernen wir Folgendes:
Was ist Suche?
Die Suche ist ein Dienstprogramm, mit dem der Benutzer Dokumente, Dateien, Medien oder andere Arten von Daten finden kann, die in einer Datenbank gespeichert sind. Die Suche basiert auf dem einfachen Prinzip, die Kriterien mit den Datensätzen abzugleichen und dem Benutzer anzuzeigen. Auf diese Weise funktioniert die grundlegendste 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. Das Hauptarbeitsprinzip besteht darin, die Daten in der Liste auf die Hälfte zu teilen, bis der erforderliche Wert gefunden und dem Benutzer im Suchergebnis angezeigt wird. Die binäre Suche wird allgemein als Halbintervallsuche oder logarithmische Suche bezeichnet .
In diesem Algorithmus-Tutorial lernen Sie:
- Was ist Suche?
- Was ist binäre Suche?
- Wie funktioniert die binäre Suche?
- Beispiel für eine binäre Suche
- Warum brauchen wir eine binäre Suche?
Wie funktioniert die binäre Suche?
Die binäre Suche funktioniert folgendermaßen:
- Der Suchvorgang wird gestartet, indem das mittlere Element des sortierten Datenarrays gefunden wird
- Danach wird der Schlüsselwert mit dem Element verglichen
- Wenn der Schlüsselwert kleiner als das mittlere Element ist, analysiert die Suche die oberen Werte zum Vergleich und Abgleich mit dem mittleren Element
- Wenn der Schlüsselwert größer als das mittlere Element ist, analysiert die Suche die unteren Werte zum Vergleich und Abgleich mit dem mittleren Element
Beispiel für eine binäre Suche
Schauen wir uns das Beispiel eines Wörterbuchs an. Wenn Sie ein bestimmtes Wort finden müssen, geht niemand jedes Wort nacheinander durch, sondern sucht zufällig die nächstgelegenen Wörter, um nach dem gewünschten Wort zu suchen.
Das obige Bild zeigt Folgendes:
- Sie haben ein Array mit 10 Ziffern und das Element 59 muss gefunden werden.
- Alle Elemente sind mit dem Index von 0 bis 9 markiert. Nun wird die Mitte des Arrays berechnet. Dazu nehmen Sie die Werte ganz links und ganz rechts des Index und teilen sie durch 2. Das Ergebnis ist 4,5, aber wir nehmen den Mindestwert. Daher ist die Mitte 4.
- Der Algorithmus löscht alle Elemente von der Mitte (4) bis zur untersten Grenze, da 59 größer als 24 ist und das Array nur noch 5 Elemente enthält.
- Jetzt 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, was 5 ist.
- An diesem Punkt wissen Sie, dass 59 nach 45 kommt. Daher wird der linke Index, der 5 ist, ebenfalls mittel.
- Diese Iterationen werden fortgesetzt, bis das Array auf nur ein Element reduziert ist oder das zu findende Element zur Mitte des Arrays wird.
Beispiel 2
Schauen wir uns das folgende Beispiel an, um die Funktionsweise der binären Suche zu verstehen
- Sie haben ein Array von sortierten Werten zwischen 2 und 20 und müssen 18 suchen.
- Der Durchschnitt der unteren und oberen Grenze ist (l + r) / 2 = 4. Der gesuchte Wert ist größer als die Mitte, die 4 ist.
- Die Array-Werte, die kleiner als der Mittelwert sind, werden aus der Suche entfernt, und Werte, die größer als der Mittelwert 4 sind, werden durchsucht.
- Dies ist ein wiederkehrender Teilungsprozess, bis der tatsächlich zu durchsuchende Artikel gefunden wird.
Warum brauchen wir eine binäre Suche?
Die folgenden Gründe machen die binäre Suche zu einer besseren Wahl für die Verwendung als Suchalgorithmus:
- Die binäre Suche arbeitet effizient mit sortierten Daten, unabhängig von der Größe der Daten
- Anstatt die Suche durchzuführen, indem die Daten in einer Sequenz durchlaufen werden, greift der binäre Algorithmus zufällig auf die Daten zu, um das erforderliche Element zu finden. Dies macht die Suchzyklen kürzer und genauer.
- Die binäre Suche führt Vergleiche der sortierten Daten basierend auf einem Ordnungsprinzip durch, als Gleichheitsvergleiche zu verwenden, die langsamer und meist ungenau sind.
- Nach jedem Suchzyklus teilt der Algorithmus die Größe des Arrays in zwei Hälften, sodass er in der nächsten Iteration nur in der verbleibenden Hälfte des Arrays funktioniert
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, bei der das erforderliche Element gefunden wird, in zwei Hälften geteilt wird.
- Der binäre Algorithmus nimmt die Mitte des Arrays, indem er die Summe der Indexwerte ganz links und ganz rechts durch 2 dividiert. Der Algorithmus entfernt nun je nach zu findendem Element entweder die untere oder die obere Grenze der Elemente aus der Mitte des Arrays .
- Der Algorithmus greift zufällig auf die Daten zu, um das erforderliche Element zu finden. Dies macht die Suchzyklen kürzer und genauer.
- Die binäre Suche führt Vergleiche der sortierten Daten basierend auf einem Ordnungsprinzip durch, als Gleichheitsvergleiche zu verwenden, die langsam und ungenau sind.
- Eine binäre Suche ist nicht für unsortierte Daten geeignet.