6.3 Die binäre Suche

Inhalt dieser Seite

6.3.1 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 ein mittleres Element und zwei Hälften links und rechts davon.

Sollte das mittlere Element mit dem Suchbegriff oder der Suchzahl übereinstimmen, ist die Suche erfolgreich beendet. Andernfalls wird entweder in der linken oder in der rechten Hälfte nach dem gleichen Verfahren weitergesucht.

Flussdiagramm der binären Suche
Autor: Ulrich Helmich 2/2026, Lizenz: Public domain

Hier sehen wir ein Flussdiagramm, das den Algorithmus der binären Suche darstellt.

Achten Sie darauf, dass ein Flussdiagramm nicht die Syntax einer Programmiersprache einhalten muss, sondern relativ frei gestaltet werden kann.

6.3.2 Veranschaulichung der binären Suche

Wir wollen nun die binäre Suche in einem Array aus int-Zahlen genauer untersuchen:

Die Suchzahl ist 31.

Mit mitte=(links+rechts)/2 berechnen wir den Index des mittleren Elementes:

mitte = (0 + 19) / 2 = 9

Achten Sie darauf, dass es sich hier um eine ganzzahlige Division handelt, von dem Ergebnis 9,5 wird also nur der ganzzahlige Anteil 9 übernommen.

Die 19 ist unser mittleres Element. Da diese Zahl nicht mit dem Suchwert übereinstimmt, müssen wir die Suche fortsetzen. Es wird nun die folgende Überprüfung durchgeführt:

array[mitte] > suchwert ?

Da der Suchwert 31 größer ist als der Wert in der Mitte (19), wird in der rechten Hälfte des Arrays weitergesucht. Der linke Grenzwert muss dann neu berechnet werden:

links = mitte+1

Damit wird das Element an Position 10 (die 21) zum neuen linken Grenzwert. Die Zahlen links der 19 und die 19 selbst können wir ab jetzt ignorieren. Mit

mitte = (10 + 19) / 2 = 14

erhalten wir das mittlere Element des rechten Teilbereichs:

Die Suchzahl 31 ist größer als die 29, also wird im rechten Teil-Array weitergesucht. Der linke Grenzwert wird jetzt auf 14 + 1 = 15 gesetzt, der rechte Grenzwert bleibt weiterhin 19.

Die neue Mitte des neuen Teilbereichs berechnet sich aus

mitte = (15 + 19) / 2 = 17

Da die Suchzahl kleiner ist als die 35, wird im linken Teil-Array weitergesucht. Der Grenzwert links = 15 bleibt bestehen, der Grenzwert rechts wird auf 16 gesetzt .

Die neue Mitte berechnet sich nach

mitte = (15 + 16) / 2 = 15

jetzt an Position 15 und hat den Wert 31:

Die Bedingung array[mitte] == suchwert ist nun erfüllt, daher kann die Suche erfolgreich mit dem Rückgabewert 15 beendet werden.

Wenn Sie mitgezählt haben, werden Sie auf fünf Vergleiche gekommen sein, die wir durchführen mussten, um die Suchzahl zu finden. Bei einer linearen Suche hätten wir deutlich mehr Vergleiche benötigt.

Allerdings hätte man die kleinen Zahlen 1, 3, 5 etc. bei einer linearen Suche genau so schnell oder sogar noch schneller gefunden als bei der binären Suche.

6.3.3 Quantitativer Vergleich binär - linear

Mathematiker würden nun eine schöne und komplexe Formel aufstellen, mit der man sofort ausrechnen kann, wie groß die durchschnittliche Suchzeit bei der binären Suche ist.

Informatiker sind da eher praktischer eingestellt. Wir schreiben uns einfach ein kleines Java-Programm, in dem wir ein sortiertes Array einmal sequentiell und einmal binär durchsuchen - und zwar nicht mit einer Suchzahl, sondern mit einer ganzen Reihe von Suchzahlen.

Die Anzahl der Vergleiche in den beiden Methoden wird mitgezählt, um am Ende kommt man zu einem quantitativen Ergebnis für die durchschnittliche Zahl der Vergleiche bei beiden Methoden.

Das Methode zur binären Suche sieht so aus:

  public int vergleicheBinaer(int[] a, int suchzahl)
    {
        int links = 0;
        int rechts = a.length - 1;
        int v = 0;

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

            v++; // == Vergleich
            if (a[mitte] == suchzahl)
            {
                return v;
            }

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

        return v;
    }

Die lokale Variable v zählt alle Vergleiche mit, die während der Suche anfallen. Die Methode vergleicheBinaer() liefert nicht den Index des gesuchten Elements (oder -1) zurück, sondern die Anzahl der notwendigen Vergleiche zum Finden der Suchzahl bzw. für die Feststellung des Nichtvorhandenseins derselben.

Die Methode für die lineare Suche ist dagegen recht einfach:

    public int vergleicheLinear(int[] a, int suchzahl)
    {
        int v = 0;

        for (int i = 0; i < a.length; i++)
        {
            v++; // == Vergleich
            if (a[i] == suchzahl)
            {
                return v;
            }
        }

        return v;
    }

Schauen wir uns nun noch die eigentliche Test-Routine an:

    public void vergleiche()
    {
        int summeBinaer = 0;
        int summeLinear = 0;

        for (int i = 1; i <= 250; i++)
        {
            summeBinaer += vergleicheBinaer(zahlen, i);
            summeLinear += vergleicheLinear(zahlen, i);
        }

        System.out.println("Summe Vergleiche (1..250):");
        System.out.println("Lineare Suche = " + summeLinear);
        System.out.println("Binäre  Suche = " + summeBinaer);
    }

Die beiden Suchverfahren werden jeweils 250 mal durchlaufen, für die Suchzahlen von 1 bis 250. Die Zahl der Vergleiche wird aufaddiert und dann ausgegeben.

Betrachten wir nun die ersten Zeilen der Klasse LinearVsBinaer:

public class LinearVsBinaer
{
    private int[] zahlen = ArrayTools.erzeugeArray(100);

    public LinearVsBinaer()
    {
        ArrayTools.fuelleArrayMitZufallszahlen(zahlen, 100, 1, 250);
        ArrayTools.selectionSortTeilarray(zahlen, 100);
        ArrayTools.zeigeArray(zahlen);
        vergleiche();
    }

    public static void main(String[] args)
    {
        new LinearVsBinaer();
    }    

Zum Erzeugen, Befüllen und Sortieren des Arrays werden Methoden aus der selbstgeschriebenen Utility-Klasse ArrayTools verwendet. Danach ruft der Konstruktor die Test-Methode vergleiche() auf. Das Array, das hier untersucht wird, besteht aus 100 zufälligen und aufsteigend sortierten int-Zahlen mit Werten zwischen 1 und 250.

Kommen wir nun zu den Ergebnissen des Programms:

    3    6   13   14   15   16   21   24   33   36
   38   41   43   43   46   50   50   56   57   59
   59   61   64   64   64   66   68   68   75   77
   80   81   83   84   92   92   94  101  105  105
  107  109  116  116  117  121  122  127  130  130
  131  145  145  146  146  153  156  156  159  159
  161  172  178  180  180  186  187  188  189  190
  190  197  197  198  210  213  217  217  220  220
  221  223  224  226  228  229  234  235  236  240
  241  243  244  244  246  246  246  248  249  250

Summe Vergleiche (1..250):
Lineare Suche = 21071
Binäre  Suche = 3086

Wenn wir das Programm noch einmal starten, werden andere Zufallszahlen erzeugt. Hier das Ergebnis eines zweiten Durchlaufs:

    3    4    8    8   10   16   17   27   31   32
   32   33   34   34   36   42   43   44   46   52
   55   59   59   60   63   64   65   66   69   72
   72   74   77   81   83   83   85   91   94   96
   98   99  104  105  107  109  111  115  116  121
  126  126  128  128  129  129  134  138  139  142
  143  143  152  154  164  167  169  173  174  176
  178  179  179  184  187  199  200  203  208  208
  211  212  213  213  213  213  215  221  221  222
  228  230  230  233  234  236  239  241  241  250

Summe Vergleiche (1..250):
Lineare Suche = 20818
Binäre  Suche = 3078

Beim ersten Durchlauf war die binäre Suche 6,83 mal schneller als die sequentielle, beim zweiten Durchlauf 6,76 mal schneller.

Offensichtlich ist die binäre Suche bei 100 Zahlen zirka fast sieben mal schneller als die sequentielle Suche, wenn man ein Array aus int-Zahlen durchsucht.

Erweitert man das Programm so, dass 1000 Zahlen erzeugt und durchsucht werden, ändert sich das Verhältnis von linearer zu binärer Suche drastisch:

Summe Vergleiche (1..2500):
Lineare Suche = 2082197
Binäre  Suche = 47046

Hier ist die binäre Suche ca. 44 mal schneller als die sequentielle. Auch ein zweiter Durchlauf ergab hier den Faktor 44.

Etwas Mathematik

Jetzt müssen wir doch noch wieder etwas mathematischer werden. Während der Zeitaufwand für die lineare Suche linear wächst: O(n), ist der Zeitaufwand für die binäre Suche ein logarithmischer: O(log(N)). Das liegt an der Halbierung des Suchraums bei jedem Schleifendurchgang.

Hier eine von ChatGPT erstellte Tabelle, die zeigt, wie die binäre Suche immer mehr an Vorteil gewinnt, je größer das zu durchsuchende Array ist:

Für die Vergleiche hat ChatGPT eine durchschnittliche Verteilung der Zufallszahlen in den sortierten Arrays angenommen.

Das Zeitverhalten der binären Suche O(log(N)) bezieht sich auf den Zweier-Logarithmus. Für solche Angaben ist es aber völlig egal, ob ein Zweier- , ein Zehner- oder ein natürlicher Logarithmus gemeint ist.

Trotzdem können wir uns die Sache noch einmal selbst anschaulich verdeutlichen:

Ein Suchalgorithmus mit dem Zeitverhalten O(log(N)) gewinnt immer mehr an Vorteil gegenüber einem Algorithmus mit einem O(N)-Zeitverhalten, je größer N ist.

6.3.4 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.