6.2 Die binäre Suche

Inhalt dieser Seite

Allgemeines zur binären Suche

Wenn die zu durchsuchenden Daten sortiert sind, kann man ein sehr viel effizienteres Suchverfahren anwenden als die lineare bzw. sequentielle Suche, nämlich die binäre Suche.

Die binäre Suche erfolgt nach dem Prinzip "Teile und herrsche". Das heißt, man teilt die zu durchsuchenden Daten in zwei Hälften und ermittelt dann, in welcher Hälfte das zu suchende Element vorkommt. Die andere Hälfte kann ignoriert werden. So wird bereits in dem ersten Suchschritt die Menge der zu durchsuchenden Daten um 50% reduziert.

Binäres Suchen
Autor: Ulrich Helmich 2025, Lizenz: Public domain

Dieses Bild veranschaulicht das binäre Suchen nach der Zahl 5 in einem aufsteigend sortierten Array.

Quelltext einer binären Suche ↑

Hier der Quelltext einer Java-Methode zur binären Suche in einem int-Array:

    public static int sucheBinaer(int[] a, int suchzahl)
    {
        if (!istSortiert(a))
        {
            throw new IllegalArgumentException
               ("Array ist nicht sortiert (aufsteigend) – Binärsuche nicht möglich.");
        }

        int links = 0;
        int rechts = a.length - 1;

        while (links <= rechts)
        {
            int mitte = (links + rechts) / 2;

            if (a[mitte] == suchzahl)
            {
                return mitte;
            }
            else if (suchzahl < a[mitte])
            {
                rechts = mitte - 1; // Mitte selbst kann ausgeschlossen werden
            }
            else
            {
                links = mitte + 1;  // Mitte selbst kann ausgeschlossen werden
            }
        }

        return -1; // nicht gefunden
    }   

Ich habe die Methode sucheBinaer() in die Utility-Klasse ArrayTools eingebaut, damit sie auch anderen Klassen zur Verfügung steht. Schauen wir uns diesen Quelltext nun Zeile für Zeile an.

Ausführliche Erklärung des Quelltextes ↑

Vorbedingungen

Die binäre Suche ist nur in sortierten Arrays anwendbar. Dies wird mit der Hilfsmethode istSortiert() überprüft, die sich in der Klasse ArrayTools befindet.

Fehlerbehandlung:

Wenn die notwendige Vorbedingung nicht erfüllt ist (das Array ist unsortiert), wird eine IllegalArgumentException ausgelöst. Dies ist eine gute Praxis, da so ein Laufzeitfehler generiert wird, der klar signalisiert, dass die Methode mit unzulässigen Daten aufgerufen wurde. Es ist besser, eine klare Fehlermeldung auszugeben, als ein fehlerhaftes oder falsches Ergebnis zu liefern. Durch die Exception wird das Problem frühzeitig erkannt und kann nicht "übersehen" werden.

Rückgabewert

public static int sucheBinaer(int[] a, int suchzahl)

Die Methode gibt den Index der gesuchten Zahl zurück, wenn diese in dem Array enthalten ist. Wenn die Zahl nicht enthalten ist, wird der Wert -1 zurückgeliefert.

1. Suchintervall initialisieren

int links = 0;
int rechts = a.length - 1;

Zu Beginn der Methode umfasst das Suchintervall das gesamte Array.

Falls das übergebene Array leer ist, hat a.length den Wert 0; dadurch wird die Variable rechts auf -1 gesetzt. In diesem Fall ist die Schleifenbedingung schon beim ersten Test nicht erfüllt, und die Methode liefert sofort -1 zurück.

2. Schleifenbedingung

while (links <= rechts)

Am Anfang ist diese Bedingung bei jedem Array mit mindestens einem Element erfüllt: links = 0, rechts = a.length-1.

Im Verlauf der Suche bedeutet diese Bedingung:

• links <= rechts: Es befindet sich noch mindestens ein Element im aktuellen Suchintervall, die Suche ist also noch nicht beendet.
• links > rechts: Das Intervall ist leer, die Suchzahl wurde nicht gefunden und die Suche kann beendet werden.

3. Berechnung der Mitte

Die Berechnung der Mitte ist ein zentraler Bestandteil des Algorithmus, da das Intervall in jedem Schritt in zwei Partitionen geteilt wird – eine linke Partition und eine rechte Partition. Das mittlere Element gilt nach dem Vergleich als "bearbeitet" und wird nicht erneut betrachtet.

int mitte = (links + rechts) / 2;

Beispiel:

Ein Array besteht aus 260 Elementen. Zu Beginn des Suchvorgangs berechnet sich die Mitte dann aus (0 + 259) / 2 = 259 / 2 = 129. Das Element mit dem Index 129 ist also beim ersten Durchlauf das mittlere Element.

4. Vergleich der Suchzahl mit der Mitte

if (a[mitte] == suchzahl) 
{
    return mitte;
}

Wenn das mittlere Element mit der Suchzahl übereinstimmt, wird die Suche sofort abgebrochen und der Index des mittleren Elementes wird als Ergebnis zurückgeliefert.

5. Intervall halbieren, zwei Partitionen erstellen

else if (suchzahl < a[mitte]) {
    rechts = mitte - 1; 
} else {
    links  = mitte + 1; 
}

Fall 1: suchzahl < a[mitte]

Die gesuchte Zahl kann nur im linken Teil des Intervalls liegen. In diesem Fall wird der Suchbereich eingeschränkt, es muss dann nur noch der linke Teil des Intervalls durchsucht werden.

Die linke Grenze dieser Partition bleibt bestehen, aber die rechte Grenze muss neu berechnet werden und wird auf mitte - 1 gesetzt. Das mittlere Elemente selbst wird nicht weiter berücksichtigt.

Fall 2: suchzahl > a[mitte]

Wenn die Suchzahl aber größer als die mittlere Zahl ist, wird der gleiche Vorgang für die rechte Hälfte des ursprünglichen Intervalls durchgeführt. Die rechte Grenze bleibt unverändert, die linke Grenze wird auf mitte + 1 gesetzt.

6. Zurück zu Punkt 2

Der Schleifendurchgang ist an dieser Stelle beendet. Wenn die Suchzahl noch nicht gefunden wurde, startet der nächste Durchlauf. Je nach Vergleichsergebnis wird jetzt entweder die linke oder die rechte Partition durchsucht.

Damit beginnt der Ablauf wieder bei Punkt 2: Die Schleifenbedingung wird erneut geprüft.

7. Suchzahl nicht gefunden

Wenn die Bedingung links <= rechts nicht mehr erfüllt ist, ist das Suchintervall leer. Die Schleife wird beendet, ohne dass die Suchzahl gefunden wurde.

Da die Methode aber einen Rückgabewert liefern muss (sonst meldet der Compiler einen Fehler), wird jetzt der Wert -1 als Ergebnis zurückgegeben.

Binäre Suchbäume und B-Bäume ↑

Das auf dieser Seite betrachtete binären Suchverfahren eignet sich sehr gut für bereits sortierte Arrays oder andere Listen. Der zentrale Vorteil des Verfahrens liegt in seiner Effizienz: Durch das wiederholte Halbieren des Arrays kann ein gesuchtes Element in logarithmischer Zeit gefunden werden. Diese Effizienz ist jedoch an eine wesentliche Voraussetzung gebunden – die Daten müssen bereits sortiert vorliegen und dürfen sich während der Suche nicht verändern.

Was aber, wenn die sortierten Daten ständig durch Einfügen neuer Daten und Löschen nicht mehr benötigter Daten durcheinander gebracht werden? Große Datenbanken können nicht nach jeder Bearbeitung neu sortiert werden, das wäre viel zu aufwendig, und der Vorteil, den die binäre Suche mit sich bringt, wäre wieder zunichte gemacht. Speichert man die Daten dagegen in einem binären Suchbaum, hat man diese Probleme nicht.

Binäre Suchbäume übertragen das Grundprinzip der binären Suche – also das schrittweise Vergleichen und Eingrenzen des Suchbereichs – auf eine dynamische Datenstruktur. Die Ordnung der gespeicherten Werte liegt dabei nicht wie bei einem sortierten Array einfach als feste Reihenfolge vor, sondern ergibt sich aus der Anordnung der Knoten im Baum. Dadurch können Suchen, Einfügen und Löschen von Daten effizient durchgeführt werden, ohne dass die gesamte Struktur jedes Mal neu sortiert werden muss.

Wenn Sie die oben verlinkten Seiten gründlich durchgearbeitet haben, dann werden Sie jetzt vielleicht enttäuscht sein, dass diese binären Suchbäume fast ausschließlich nur in Informatik-Lehrbüchern für Schulen und Hochschulen vorkommen. In der realen Welt verwendet man diese Art von Bäumen so gut wie gar nicht.

Für sehr große Datenmengen, insbesondere wenn diese nicht vollständig im Hauptspeicher gehalten werden können, stoßen einfache binäre Suchbäume nämlich an ihre Grenzen. Hier kommen die von Rudolf Bayer und Edward McCreight Anfang der 70er Jahre entwickelten B-Bäume ins Spiel. Diese B-Bäume erweitern das Konzept des Suchbaums, so dass auch in externen Speichern wie Festplatten oder SSDs effizient gesucht werden kann. B-Bäume bilden sozusagen das Fundament moderner Datenbank- und Dateisysteme.