Binäre Suche (mit Java-Code)

Wir Entwickler stehen oft vor der Aufgabe in einem sortierten Array (oder in einer Liste) die Position eines gesuchten Elements zu bestimmen. Der einfachste Ansatz wäre das Array von links nach rechts zu durchlaufen und dabei jedes Element mit dem gesuchten Element abzugleichen. Das nennt man "lineare Suche".

Deutlich schneller geht es mit der "binären Suche". In diesem Artikel erfährst du:

• Wie funktioniert die Binärsuche?
• Wie implementiert man die binäre Suche in Java (rekursiv und iterativ)?
• Welche binären Suchfunktionen stellt das JDK zur Verfügung?
• Wie schnell ist die binäre Suche im Vergleich zur linearen Suche?
• Wann ist es sinnvoll in einer LinkedList binär zu suchen?

Den Code zum Artikel findest du in diesem GitHub-Repository.

Binäre Suche – ein Beispiel

Wenn wir früher ein unbekanntes Wort übersetzen wollten, hatten wir dafür keine App, sondern mussten dieses in einem Wörterbuch nachschlagen. Theoretisch könnte man nun von vorne nach hinten jede Seite von links oben nach rechts unten nach dem gewünschten Wort durchsuchen.

Mit etwas Glück finden wir das Wort auf den ersten Seiten des Buches. Wenn wir Pech haben, finden wir es erst gegen Ende des Buches – oder gar nicht (das würden wir erst auf der allerletzten Seite feststellen). Auch bei relativ weit vorne liegenden Wörtern (wie z. B. "Binärsuche") müssten wir so ziemlich lange suchen.

Diese Vorgehensweise nennt sich "lineare Suche". Das folgende Bild zeigt ein vereinfachtes Beispiel mit Zahlen statt Wörtern. Gesucht werden soll die Position der Zahl 61 im dargestellten Array.

In diesem vereinfachten Beispiel benötigen wir sechs Schritte, um die 61 zu finden.

Natürlich würde in einem Wörterbuch niemand auf diese Weise suchen. Stattdessen schlagen wir das Buch ungefähr in der Mitte auf und schauen, ob das Wort alphabetisch davor oder danach einzuordnen ist. Wir wissen somit, in welcher Hälfte des Buchs sich das Wort befindet und können die andere Hälfte ignorieren. Danach suchen wir wieder die Mitte und schränken den Suchbereich erneut auf die Hälfte (also insgesamt ein Viertel) ein. Mit jedem weiteren Suchschritt halbieren wir die Anzahl der verbleibenden Seiten. Auf diese Weise kommen wir in relativ wenigen Schritten zur Zielseite – und auf der Zielseite zum gesuchten Wort.

Das nennt sich dann "binäre Suche". Das folgende Bild macht deutlich, dass die Suche so wesentlich schneller zum Ergebnis führt als die lineare Suche:

Mit der Binärsuche brauchen wir lediglich drei Schritte:

1. Im ersten Schritt vergleichen wir den gesuchten Wert 61 mit dem mittleren Element 36. Der gesuchte Wert ist größer, muss sich also rechts von der 36 befinden.
2. Im zweiten Schritt vergleichen wir die 61 mit dem mittleren Element des rechten Bereichs, der 79. Der gesucht Wert ist kleiner, muss sich also links von der 79 befinden.
3. Zwischen 36 und 79 befindet sich nur noch ein Element. Auch dieses müssen wir noch einmal mit dem gesuchten Element vergleichen. In diesem Beispiel haben wir das gesuchte Element 61 gefunden. Hier hätte sich aber auch eine andere Zahl zwischen 36 und 79 befinden können. Das hätte bedeutet, dass das Array gar keine 61 enthält.

Die Binärsuche macht selbstverständlich nur dann Sinn, wenn die Wörter im Wörterbuch (so wie die Zahlen im Beispiel) sortiert sind. Würden die Wörter in zufälliger Reihenfolge abgedruckt sein, bliebe uns nichts anderes übrig als Wort für Wort – also linear – zu suchen.

Binäre Suche – Pseudocode

Im folgenden Pseudocode bezeichnen wir das gesuchte Element mit "Schlüssel" (im Englischen wird es mit "key" bezeichnet).

1. Bestimme die mittlere Position des zu durchsuchenden Bereichs des Arrays.
2. Lese das Element an der mittleren Position.
3. Vergleiche den Schlüssel mit dem mittleren Element:
   • Ist der Schlüssel gleich dem mittleren Element, dann haben wir das Ziel erreicht. Gebe die mittlere Position als Ergebnis zurück.
   • Ist der Schlüssel kleiner als das mittlere Element, dann führe die Binärsuche im Teilarray links von der mittleren Position aus. Es sei denn, dieses Teilarray hat die Länge 0, dann ist die Suche ohne Ergebnis beendet.
   • Ist der Schlüssel größer als das mittlere Element, dann führe die Binärsuche im Teilarray rechts von der mittleren Position aus. Es sei denn, dieses Teilarray hat die Länge 0, dann ist die Suche ohne Ergebnis beendet.

Implementierung von binärer Suche in Java

Die Binärsuche kann rekursiv oder iterativ implementiert werden.

Binäre Suche rekursiv

Die Pseudocode für die binäre Suche aus dem vorherigen Kapitel legt eine rekursive Implementierung nahe.

Die rekursive Implementierung in Java für ein Array von int-Primitiven sieht wie folgt aus:

public static int binarySearchRecursively(int[] array, int key) {
  return binarySearchRecursively(array, 0, array.length, key);
}

public static int binarySearchRecursively(
    int[] array, int fromIndex, int toIndex, int key) {
  if (toIndex <= fromIndex) return -1;

  int mid = (fromIndex + toIndex) >>> 1;
  int midVal = array[mid];

  if (key == midVal) {
    return mid;
  } else if (key < midVal) {
    return binarySearchRecursively(array, fromIndex, mid, key);
  } else {
    return binarySearchRecursively(array, mid + 1, toIndex, key);
  }
}Code-Sprache: Java (java)

Den Code findest du im GitHub-Repository in der Klasse BinarySearch ab Zeile 12. Passende Unit-Tests dazu gibt es in BinarySearchTest.

Wichtig ist hierbei die mittlere Position mid mittels "unsigned right shift" zu berechnen:

int mid = (fromIndex + toIndex) >>> 1

Und nicht wie folgt:

int mid = (fromIndex + toIndex) / 2

Für den Fall dass die Summe größer ist als Integer.MAX_VALUE, würde die zweite Variante zu einem Overflow bzw. einem "Roll Over" führen, und das Ergebnis wäre eine negative Zahl.

Ohne den >>>-Operator wäre auch folgender Weg korrekt:

int mid = fromIndex + (toIndex - fromIndex) / 2;

Aber das ist längst nicht so cool ;-)

Binäre Suche iterativ

Rekursion benötigt zusätzliche CPU-Zyklen und zusätzlichen Speicherplatz auf dem Heap. Daher sind iterative Implementierungen in der Regel vorzuziehen.

Die entsprechende iterative Java-Implementierung für ein int-Array sieht wie folgt aus:

public static int binarySearchIteratively(int[] array, int key) {
  return binarySearchIteratively(array, 0, array.length, key);
}

public static int binarySearchIteratively(
    int[] array, int fromIndex, int toIndex, int key) {
  int low = fromIndex;
  int high = toIndex;

  while (low < high) {
    int mid = (low + high) >>> 1;
    int midVal = array[mid];

    if (key == midVal) {
      return mid;
    } else if (key < midVal) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }

  return -1;
}Code-Sprache: Java (java)

Die Variablen low und high sind hier nicht zwingend erforderlich. Man könnte innerhalb der while-Schleife auch fromIndex und toIndex verändern. Methodenparameter zu ändern gilt jedoch in der Regel als unsauberes Design.

Auch diesen Code findest du in der Klasse BinarySearch ab Zeile 52. Die Unit-Tests in BinarySearchTest ab Zeile 64.

Binäre Suche im JDK

Binäre Suche in Arrays müssen wir natürlich nicht selbst implementieren. Das JDK bietet bereits entsprechende Methoden für Arrays aller primitiven Datentypen und für Objekt-Arrays in der java.util.Arrays-Klasse. Außerdem bietet es eine Methode für die Binärsuche in Listen in der java.util.Collections-Klasse.

Arrays.binarySearch()

In einem int-Array können wir beispielsweise wie folgt suchen:

int[] array = new int[] {10, 19, 23, 25, 36, 61, 79, 81, 99};
int posOf36 = Arrays.binarySearch(array, 36);Code-Sprache: Java (java)

Collections.binarySearch()

In einer entsprechenden ArrayList von Integer-Objekten können wir wie folgt suchen:

List<Integer> list = new ArrayList<>(List.of(10, 19, 23, 25, 36, 61, 79, 81, 99));
int posOf36 = Collections.binarySearch(list, 36);Code-Sprache: Java (java)

Achtung: Die Methode Collections.binarySearch() kann für jede Klasse aufgerufen werden, die das List-Interface implementiert. Also beispielsweise auch für LinkedList.

In einer verketteten Liste kann allerdings nicht direkt, sondern nur per Iteration auf ein bestimmtes Element zugegriffen werden, womit wir (fast) wieder bei der linearen Suche angekommen sind. Mehr dazu – und warum die Binärsuche auf einer LinkedList dennoch sinnvoll sein kann – erfährst du im nächsten Kapitel.

Zeitkomplexität von binärer Suche

Bei der binären Suche halbieren wir mit jedem Suchschritt die Anzahl der noch zu durchsuchenden Einträge. Oder anders herum: wenn sich die Anzahl der Einträge verdoppelt, brauchen wir nur einen Suchschritt mehr.

Dies entspricht logarithmischem Aufwand, also O(log n).

Mehr über die O- (bzw. Landau-) Notation erfährst du hier: O-Notation und Zeitkomplexität – anschaulich erklärt

Laufzeit von binärer Suche

Mit dem Programm BinarySearchRuntime aus dem GitHub-Repository können wir die theoretisch hergeleitete Zeitkomplexität überprüfen. Das Programm generiert zufällige Arrays mit 10.000 bis 200.000.000 Elementen und sucht darin nach einem zufällig ausgewählten Element.

Da die Zeiten im Bereich von Nanosekunden liegen, wird pro Messung nach 100 verschiedenen Keys gesucht. Die Messung wird für jede Array-Größe 100 mal wiederholt; danach wird der Median ausgegeben. Der folgende Graph zeigt die mittlere Laufzeit in Abhängigkeit von der Array-Größe:

Der logarithmische Verlauf ist sehr gut zu erkennen.

Vergleich binäre Suche vs. lineare Suche

Bei der linearen Suche finden wir im best case das gesuchte Element im ersten Schritt. Im worst case müssen wir das komplette Array durchsuchen. Im average case die Hälfte der Einträge. Bei n Einträgen sind das n/2 Suchschritte. Die Dauer der Suche steigt also linear mit der Anzahl der Einträge. Wir sagen auch:

Die Zeitkomplexität der linearen Suche beträgt O(n).

Mit dem Programm LinearSearchRuntime können wir die Laufzeit der linearen Suche messen. Die folgende Grafik zeigt den Vergleich der Laufzeiten von binärer und der linearen Suche. Ich musste den Ausschnitt auf 100.000 Elemente verkleinern, um überhaupt noch einen Anstieg der Messwerte für die Binärsuche erkennen zu können:

Der lineare Aufwand der linearen Suche ist sehr gut zu erkennen. Auch wird deutlich, dass die binäre Suche um Größenordnungen schneller ist als die lineare.

Laufzeit von binärer Suche für kleine Arrays

Aufgrund der höheren Komplexität des Codes der binären Suche kann die lineare Suche für sehr kleine Arrays schneller sein. Das folgende Diagramm zeigt einen Ausschnitt des Vergleichs der Laufzeiten für bis zu 500 Elemente. Jeder Messpunkt ist der Median aus 100 Messungen mit jeweils 10.000 Wiederholungen.

Das bestätigt die Vermutung. Für Arrays bis maximal ca. 230 Elemente ist die lineare Suche schneller als die binäre. Das ist natürlich keine allgemein gültige Aussage, sondern gilt erstmal nur für meinen Laptop und das verwendete JDK.

Man sieht auch noch einmal schön das lineare Wachstum – O(n) – im Vergleich zum logarithmischen Wachstum – O(log n).

Laufzeit von binärer Suche bei einer LinkedList

Im Kapitel Binäre Suche im JDK habe ich erwähnt, dass die Methode Collections.binarySearch() auch auf eine LinkedList angewendet werden kann. Collections.binarySearch() unterscheidet intern nach Listen, die das RandomAccess-Interface implementieren, wie z. B. ArrayList, und nach anderen Listen. Bei Listen mit "random access" wird eine reguläre binäre Suche durchgeführt.

Um bei Listen ohne "random access" auf das mittlere Element zugreifen zu können, müssen wir den Elementen vom Anfang bis zur Mitte Element für Element folgen. Von dort müssten wir dann wiederum zur Mitte der linken oder rechten Hälfte der Liste Element für Element folgen. Die folgende Grafik soll dies verdeutlichen:

Um beispielsweise die Position der 19 zu suchen, müssten wir erst den orangenen Pfeilen zur Mitte folgen, dann den blauen Pfeilen zurück zur 23, und schließlich dem gelben Pfeil zur 19.

Das funktioniert so nur bei einer doppelt verketteten Liste. Bei einer einfach verketteten Liste müsste man für die Iteration nach links immer wieder an den Anfang springen und von dort wieder den Pfeilen nach rechts folgen.

Egal ob einfach oder doppelt verkettet – wir müssen auf jeden Fall über mehr Elemente iterieren als bei der linearen Suche. Während wir bei der linearen Suche im Durchschnitt n/2 Suchschritte haben, iterieren wir bei der binären Suche allein beim ersten Schritt zur Mitte schon über n/2 Elemente. Beim zweiten Schritt noch einmal über n/4 Elemente, beim dritten Schritt über n/8 Elemente, usw.

Auf den ersten Blick ergibt die Binärsuche in einer LinkedList also keinen Sinn.

Wann ist die Binärsuche in einer LinkedList sinnvoll?

Dennoch kann die Binärsuche für eine LinkedList schneller sein als eine lineare Suche. Zwar müssen wir (wie im vorherigen Abschnitt gezeigt) über mehr Elemente iterieren – die Anzahl der Vergleiche bleibt aber in der Größenordnung O(log n)!

Je nach Kosten der Vergleichsfunktion – bei einem Objekt können diese deutlich höher ausfallen als bei einem primitiven Datentyp – kann dies einen erheblichen Unterschied ausmachen. Solltest du also jemals in einer LinkedList suchen müssen, dann lohnt es sich auf jeden Fall die Binärsuche mit Collections.binarySearch() auszuprobieren und mit der linearen Suche zu vergleichen.

Fazit

Dieser Artikel hat die Funktionsweise der binären Suche und ihre Vorteile gegenüber linearer Suche bei sortierten Arrays und Listen aufgezeigt. Die theoretisch hergeleitete Zeitkomplexität wurde an einem Beispiel nachgewiesen. Außerdem wurde gezeigt, dass die Binärsuche auch bei einer doppelt verketten Liste sinnvoll sein kann.

Ein sehr ähnliches Verfahren ist die Suche in einem Binären Suchbaum.

Wenn dir der Artikel gefallen hat, hinterlasse mir gerne einen Kommentar oder teile den Artikel über einen der Share-Buttons am Ende. Möchtest du informiert werden, wenn die nächsten Artikel veröffentlicht werden, dann trage dich über das folgende Formular in meinen Newsletter ein.