Binärer Suchalgorithmus mit BEISPIEL

Bevor wir uns mit der binären Suche beschäftigen, wollen wir erst einmal lernen, was Suchen überhaupt ist.

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?

Die Binärsuche ist ein fortgeschrittener Suchalgorithmus, der Daten aus einer sortierten Liste von Elementen findet und abruft. Ihr Funktionsprinzip besteht darin, die Liste so lange zu halbieren, bis der gesuchte Wert gefunden und dem Benutzer im Suchergebnis angezeigt wird. Die Binärsuche ist allgemein bekannt als … Halbintervallsuche oder die logarithmische Suche.

Wie funktioniert die binäre Suche?

Die binäre Suche funktioniert folgendermaßen:

• Der Suchprozess beginnt mit dem Auffinden des mittleren Elements des sortierten Datenarrays.
• Anschließend wird der Schlüsselwert mit dem Element verglichen.
• Ist der Schlüsselwert kleiner als das mittlere Element, analysiert die Suche die Werte oberhalb des mittleren Elements zum Vergleich und zur Übereinstimmung.
• Falls der Schlüsselwert größer als das mittlere Element ist, analysiert die Suche die niedrigeren Werte bis zum mittleren Element zum Vergleich und zur Übereinstimmung.

Binärer Suchalgorithmus (Pseudocode)

Die binäre Suche lässt sich als kurze, iterative Routine schreiben. Sie verwendet zwei Zeiger, low und high, und verkleinert den Suchbereich, bis das Ziel gefunden ist oder der Bereich leer ist.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

Die Routine gibt bei Erfolg den Index des Ziels zurück und -1, falls der Wert nicht vorhanden ist. Da sich der Bereich bei jedem Durchlauf halbiert, wird die Schleife höchstens log₂(n) Mal ausgeführt.

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 sind mit einem Index von 0 bis 9 gekennzeichnet. Nun wird der mittlere Wert des Arrays berechnet. Dazu teilt man den linken und rechten Index durch 2. Das Ergebnis ist 4.5, aber wir runden ab. Daher ist der mittlere Wert 4.
3. Der Algorithmus entfernt alle Elemente von der Mitte (4) bis zur kleinsten Grenze, da 59 größer als 24 ist, und das Array enthält nun nur noch 5 Elemente.
4. Nun ist 59 größer als 45 und kleiner als 63. Der Mittelwert ist 7. Daher wird der rechte Indexwert zum Mittelwert − 1, was 6 ergibt, und der linke Indexwert bleibt unverändert bei 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

Um die Funktionsweise der Binärsuche zu verstehen, sehen wir uns das folgende Beispiel an.

1. Sie haben ein Array mit sortierten Werten im Bereich von 2 bis 20 und müssen 18 finden.
2. Der Mittelwert der unteren und oberen Grenze beträgt (l + r) / 2 = 4. Der gesuchte Wert ist größer als der Mittelwert, der 4 beträgt.
3. Die Arraywerte unterhalb des Mittelwerts werden von der Suche ausgeschlossen, und es wird nach Werten oberhalb des Mittelwerts 4 gesucht.
4. Dabei handelt es sich um einen wiederkehrenden Teilungsvorgang, bis der eigentliche Suchgegenstand gefunden ist.

Warum brauchen wir eine binäre Suche?

Aus folgenden Gründen ist die binäre Suche als Suchalgorithmus besser geeignet:

• Die binäre Suche funktioniert effizient mit sortierten Daten, unabhängig von der Größe der Daten.
• 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 die sortierten Daten anhand eines Ordnungsprinzips verglichen, anstatt Gleichheitsvergleiche durchzuführen, die langsamer und meist ungenau sind.
• Nach jedem Suchzyklus halbiert der Algorithmus die Größe des Arrays; daher arbeitet er in der nächsten Iteration nur noch mit der verbleibenden Hälfte des Arrays.

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

Binäre Suche vs. Lineare Suche

Binäre Suche und lineare Suche sind die beiden gebräuchlichsten Methoden, um einen Wert in einer Sammlung zu finden. Die folgende Tabelle verdeutlicht die Unterschiede:

Kurz gesagt, ist die binäre Suche bei großen sortierten Daten wesentlich schneller, während die lineare Suche einfacher und die einzige Option ist, wenn die Daten nicht sortiert sind.

Häufig gestellte Fragen