In der Serie "Named Problems" stelle ich dir klassische, namentlich bekannte Algorithmus-Probleme vor, die seit Jahrzehnten in Ausbildung, Studium und Interviews verwendet werden. Anhand verständlicher Problemstellungen wie FizzBuzz, Türme von Hanoi oder dem Sieb des Eratosthenes lernst du hier, algorithmisch zu denken, Lösungsstrategien zu entwickeln und diese sauber in Java umzusetzen.

Die binäre Suche ist ein Klassiker unter den Algorithmen: Du willst ein Element in einer sortierten Liste finden, ohne jedes Element einzeln anzuschauen.

Sie ist so bekannt, weil sie ein sehr gutes Beispiel für Divide and Conquer ist: Du teilst das Problem immer wieder in kleinere Teile, bis nur noch wenig übrig ist.

In diesem Artikel lernst du, woran du erkennst, ob binäre Suche passt, wie du sie Schritt für Schritt umsetzt und welche typischen Fehler dabei passieren.

Am Ende hast du zwei Java-Varianten: eine klare, straightforward Lösung und eine Alternative, die das Prinzip rekursiv zeigt.

 

Problemstellung

Gegeben ist ein sortiertes Array von Zahlen. Du sollst einen Zielwert finden und den Index zurückgeben.

  • Das Array ist aufsteigend sortiert (z.B. [1, 4, 7, 10]).
  • Wenn der Wert enthalten ist, gib seinen Index zurück.
  • Wenn der Wert nicht enthalten ist, gib -1 zurück.
  • Du sollst möglichst nicht linear über alle Elemente laufen (wenn es sich vermeiden lässt).

Mini-Beispiel:

  1. Eingabe: Array [1, 3, 5, 7, 9], Ziel 7 => Ausgabe: 3
  2. Eingabe: Array [2, 4, 6, 8], Ziel 5 => Ausgabe: -1
  3. Eingabe: Array [], Ziel 1 => Ausgabe: -1

 

Die Idee dahinter

Die binäre Suche nutzt die Sortierung aus. Statt alles zu prüfen, schaust du immer in die Mitte des aktuellen Bereichs.

Dann entscheidest du:

  • Ist der Mittelwert gleich dem Ziel? Dann bist du fertig.
  • Ist der Mittelwert kleiner als das Ziel? Dann kann das Ziel nur rechts liegen.
  • Ist der Mittelwert größer als das Ziel? Dann kann das Ziel nur links liegen.

Kurze Visualisierung als Liste (Bereich wird immer kleiner):

  • Start: ganzer Bereich low..high
  • Nach Schritt 1: nur linke oder rechte Hälfte
  • Nach Schritt 2: wieder nur eine Hälfte davon
  • Weiter so, bis gefunden oder Bereich leer

 

Schritt für Schritt zur Lösung

  1. Setze zwei Grenzen: low startet bei 0, high startet bei array.length - 1.
  2. Solange der Bereich nicht leer ist (also low <= high), suche die Mitte.
  3. Berechne mid so, dass es keine Überläufe gibt: low + (high - low) / 2.
  4. Vergleiche array[mid] mit dem Zielwert.
  5. Bei Treffer gib mid zurück.
  6. Wenn der Mittelwert kleiner ist, verschiebe low nach rechts: low = mid + 1.
  7. Wenn der Mittelwert größer ist, verschiebe high nach links: high = mid - 1.
  8. Wenn die Schleife endet, ist der Wert nicht enthalten: gib -1 zurück.

 

Java-Implementierung (Variante A: straightforward)

public class BinarySearchStraightforward {

  public static void main(String[] args) {
    int[] numbers = {1, 3, 5, 7, 9, 12, 20};

    System.out.println(indexOf(numbers, 7));   // 3
    System.out.println(indexOf(numbers, 2));   // -1
    System.out.println(indexOf(numbers, 20));  // 6
    System.out.println(indexOf(numbers, 1));   // 0
  }

  public static int indexOf(int[] sorted, int target) {
    if (sorted == null || sorted.length == 0) {
      return -1;
    }

    int low = 0;
    int high = sorted.length - 1;

    while (low <= high) {
      int mid = low + (high - low) / 2;
      int value = sorted[mid];

      if (value == target) {
        return mid;
      }

      if (value < target) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }

    return -1;
  }
}

Diese Variante ist die typische, iterative Umsetzung. Sie arbeitet nur mit low, high und mid und verkleinert den Bereich pro Schleifendurchlauf. Das ist gut lesbar und in der Praxis meist die erste Wahl. Die Laufzeit wächst dabei sehr langsam, weil der Suchbereich jedes Mal halbiert wird.

 

Java-Implementierung (Variante B: Alternative oder Verbesserung)

public class BinarySearchRecursive {

  public static void main(String[] args) {
    int[] numbers = {1, 3, 5, 7, 9, 12, 20};

    System.out.println(indexOf(numbers, 7));   // 3
    System.out.println(indexOf(numbers, 2));   // -1
    System.out.println(indexOf(numbers, 20));  // 6
  }

  public static int indexOf(int[] sorted, int target) {
    if (sorted == null || sorted.length == 0) {
      return -1;
    }

    return indexOf(sorted, target, 0, sorted.length - 1);
  }

  private static int indexOf(int[] sorted, int target, int low, int high) {
    if (low > high) {
      return -1;
    }

    int mid = low + (high - low) / 2;
    int value = sorted[mid];

    if (value == target) {
      return mid;
    }

    if (value < target) {
      return indexOf(sorted, target, mid + 1, high);
    }

    return indexOf(sorted, target, low, mid - 1);
  }
}

Hier siehst du Divide and Conquer sehr direkt: Jeder Aufruf teilt den Bereich und ruft sich dann mit der passenden Hälfte erneut auf. Wichtig ist die Abbruchbedingung low > high, sonst läuft die Rekursion endlos. In Java ist die iterative Variante oft bevorzugt, weil sie ohne Rekursions-Overhead auskommt.

 

Beispiel: Eingabe und Ausgabe

Beispiel 1: Array [1, 3, 5, 7, 9], Ziel 7 => Rückgabewert 3

Beispiel 2: Array [2, 4, 6, 8], Ziel 5 => Rückgabewert -1

Beispiel 3: Array [10], Ziel 10 => Rückgabewert 0

 

Typische Fehler

  • Array nicht sortiert: Binäre Suche setzt Sortierung voraus. Ohne Sortierung ist das Ergebnis unzuverlässig.
  • Falsche Schleifenbedingung: while (low < high) statt while (low <= high) kann den letzten Kandidaten überspringen.
  • Off-by-one bei Updates: low = mid oder high = mid kann zu Endlosschleifen führen. Richtig ist mid + 1 oder mid - 1.
  • Mid falsch berechnet: (low + high) / 2 kann bei großen Indizes überlaufen. Besser: low + (high - low) / 2.
  • Abbruchbedingung bei Rekursion fehlt: Ohne if (low > high) endet die Rekursion nicht sicher.
  • Rückgabewert uneinheitlich: Mal null, mal -1, mal Exception. Lege eine klare Regel fest (hier: -1).
  • Null/Leer-Array nicht behandelt: Ein schneller Guard-Check spart NPEs und Sonderfälle.

 

Fazit

Du hast gesehen, wie die binäre Suche ein sortiertes Problem durch Divide and Conquer schnell kleiner macht. Mit low, high und einer sauberen mid-Berechnung bekommst du eine robuste Lösung. Variante A ist in Java meist die praktische Standardwahl, Variante B zeigt das Prinzip besonders anschaulich mit Rekursion.