Binary Search und Varianten: Lower Bound, Rotation, Antwortsuche

1. Überblick

Binäre Suche ist ein Suchalgorithmus für sortierte Daten mit einer Zeitkomplexität von O(log n). Die Idee ist sehr einfach, aber die Implementierung ist fehlbar: unendliche Schleifen, Off-by-One-Fehler, Ganzzahlüberläufe bei der Berechnung von mid.

Dieser Artikel geht von der Grundversion bis zu häufig vorkommenden Varianten: Finden des ersten/letzten Auftretens, Zählen von Vorkommen, Suche in rotiertem Array und binäre Suche auf die Antwort. Danach hast du ein fehlerminimiertes Implementierungsgerüst mit Tests zur Verifikation.

2. Grundlegende binäre Suche

Angenommen, du hast ein nach Preis aufsteigend sortiertes Array von Produktpreisen und möchtest die Position eines bestimmten Preises finden:

public final class PriceSearch {

    public static int search(int[] prices, int target) {
        int lo = 0;
        int hi = prices.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (prices[mid] == target) {
                return mid;
            }
            if (prices[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] prices = {100, 150, 200, 350, 500};
        System.out.println(search(prices, 350));
        System.out.println(search(prices, 300));
    }
}

Erklärung:

• lo und hi bilden ein geschlossenes Intervall [lo, hi]. Dies ist der Bereich, in dem sich target befinden kann.
• Die Bedingung lo <= hi bedeutet, dass die Schleife läuft, solange das Intervall mindestens ein Element enthält.
• mid = lo + (hi - lo) / 2 verhindert Ganzzahlüberläufe. Die Schreibweise (lo + hi) / 2 würde überläuft, wenn lo + hi Integer.MAX_VALUE überschreitet. Eine äquivalente Schreibweise ist (lo + hi) >>> 1.
• Nach jedem Schritt wird mid aus dem Intervall entfernt (mid + 1 oder mid - 1), sodass sich das Intervall immer verengt und die Schleife garantiert terminiert.

Ergebnis:

3
-1

Diese Version reicht aus, wenn das Array keine doppelten Elemente hat und du nur „existiert oder nicht” wissen musst. Bei doppelten Elementen gibt sie eine beliebige Position in der Gruppe zurück. Normalerweise ist das nicht, was du willst.

3. Lower Bound und Upper Bound

Die zwei wichtigsten Varianten sind:

• Lower Bound: Der erste Index, bei dem a[i] >= target ist.
• Upper Bound: Der erste Index, bei dem a[i] > target ist.

Beide geben immer einen Index in [0, n] zurück, auch wenn target nicht im Array vorhanden ist. Dieser Index ist genau die Einfügeposition, um das Array sortiert zu halten.

public final class Bounds {

    public static int lowerBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;              // halboffenes Intervall [lo, hi)
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    public static int upperBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

Unterschiede zur Grundversion:

• Wir verwenden ein halboffenes Intervall [lo, hi), daher wird hi mit a.length initialisiert und die Schleifenbedingung ist lo < hi.
• Wenn a[mid] die Bedingung „ausreichend groß” erfüllt, setzen wir hi = mid, nicht mid - 1, da mid immer noch die Antwort sein könnte.
• Die beiden Funktionen unterscheiden sich nur im Zeichen < und <=.

Versuchen wir es mit einem Array mit doppelten Elementen:

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Bounds.lowerBound(prices, 200)); // 1
System.out.println(Bounds.upperBound(prices, 200)); // 4
System.out.println(Bounds.lowerBound(prices, 300)); // 4
System.out.println(Bounds.lowerBound(prices, 900)); // 6

1
4
4
6

Mit 300 bedeutet das Ergebnis 4, dass beim Einfügen von 300 es vor 350 stünde. Mit 900 bedeutet ein Ergebnis gleich n, dass alle Elemente kleiner sind.

3.1. Erste Position, letzte Position und Vorkommen

Aus den beiden obigen Funktionen ergeben sich sofort die Lösungen für häufige Probleme:

public static int firstIndexOf(int[] a, int target) {
    int i = Bounds.lowerBound(a, target);
    return (i < a.length && a[i] == target) ? i : -1;
}

public static int lastIndexOf(int[] a, int target) {
    int i = Bounds.upperBound(a, target) - 1;
    return (i >= 0 && a[i] == target) ? i : -1;
}

public static int count(int[] a, int target) {
    return Bounds.upperBound(a, target) - Bounds.lowerBound(a, target);
}

Mit prices von oben und target = 200 erhalten wir firstIndexOf = 1, lastIndexOf = 3, count = 3. Wichtig zu merken: Prüfe immer auf Grenzen i < a.length (oder i >= 0), bevor du a[i] zugreifst.

3.2. Elemente in einem Bereich zählen

Eine praktische Anwendung ist, die Anzahl der Bestellungen mit Wert im Bereich [min, max] zu zählen:

public static int countInRange(int[] sortedTotals, int min, int max) {
    return Bounds.upperBound(sortedTotals, max) - Bounds.lowerBound(sortedTotals, min);
}

Mit {100, 200, 200, 200, 350, 500} und dem Bereich [150, 400]: upperBound(400) = 5, lowerBound(150) = 1, also ist das Ergebnis 4. Jede Abfrage kostet nur O(log n), ohne das ganze Array durchsuchen zu müssen.

4. Suche in rotiertem Array

Ein rotiertes Array ist ein sortiertes Array, das an einem Punkt „geschnitten” und die beiden Teile getauscht wurden, z.B. {40, 50, 60, 10, 20, 30}. Das Array ist nicht mehr vollständig aufsteigend, aber mindestens eine Hälfte um mid ist noch geordnet. Das nutzen wir, um zu entscheiden, in welche Richtung es weitergehen soll:

public static int searchRotated(int[] a, int target) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (a[mid] == target) {
            return mid;
        }
        if (a[lo] <= a[mid]) {                 // linke Hälfte ist sortiert
            if (a[lo] <= target && target < a[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {                               // rechte Hälfte ist sortiert
            if (a[mid] < target && target <= a[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return -1;
}

Erklärung:

• a[lo] <= a[mid] zeigt, dass das Intervall [lo, mid] aufsteigend ist. Wenn target im Wertebereich dieses Intervalls liegt, verengen wir nach links. Sonst nach rechts.
• Im anderen Fall ist das Intervall [mid, hi] aufsteigend und wir argumentieren symmetrisch.

System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 20));
System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 45));

4
-1

Hinweis: Diese Implementierung setzt voraus, dass das Array keine doppelten Elemente hat. Mit einem Array wie {2, 2, 2, 3, 2} kann die Bedingung a[lo] <= a[mid] nicht mehr unterscheiden, welche Hälfte sortiert ist. In diesem Fall musst du auch den Fall a[lo] == a[mid] verarbeiten, indem du lo um eins erhöhst, und die worst-case-Komplexität wird zu O(n).

5. Binäre Suche auf die Antwort

Dies ist die mächtigste Variante. Sie sucht nicht im Array, sondern nach dem kleinsten Wert, der eine Bedingung erfüllt. Die einzige Voraussetzung ist, dass das Prädikat monoton sein muss: Wenn x erfüllt wird, erfüllen auch alle größeren Werte x. Mit anderen Worten, die Folge der Ergebnisse hat die Form false, false, ..., true, true.

Wir schreiben eine generische Funktion:

import java.util.function.LongPredicate;

public final class AnswerSearch {

    /** Der kleinste Wert in [lo, hi], bei dem ok true zurückgibt. Annahme: ok(hi) == true. */
    public static long firstTrue(long lo, long hi, LongPredicate ok) {
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (ok.test(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

Diese Funktion hat die gleiche Struktur wie lowerBound. Tatsächlich ist lowerBound nur ein Spezialfall mit dem Prädikat a[i] >= target.

Anwendung auf ein praktisches Problem: Ein Lager hat eine feste Liste von Paketen und muss sie innerhalb von maxDays Tagen liefern. Jeden Tag lädt der Wagen aufeinanderfolgende Pakete, wobei die Gesamtlast die Tragfähigkeit nicht überschreitet. Wie hoch ist die minimale Tragfähigkeit?

import java.util.Arrays;

public final class ShippingPlanner {

    public static long minCapacity(int[] weights, int maxDays) {
        long lo = Arrays.stream(weights).max().orElse(0);
        long hi = Arrays.stream(weights).asLongStream().sum();
        return AnswerSearch.firstTrue(lo, hi, cap -> canShip(weights, maxDays, cap));
    }

    static boolean canShip(int[] weights, int maxDays, long capacity) {
        int days = 1;
        long load = 0;
        for (int w : weights) {
            if (load + w > capacity) {
                days++;
                load = 0;
            }
            load += w;
        }
        return days <= maxDays;
    }

    public static void main(String[] args) {
        System.out.println(minCapacity(new int[]{3, 2, 2, 4, 1, 4}, 3));
    }
}

Erklärung:

• lo ist das schwerste Paket, da der Wagen mindestens jedes Paket tragen können muss. hi ist das Gesamtgewicht, da dann nur noch ein Tag benötigt wird. Also garantiert ok(hi) true.
• canShip simuliert einen gierigen Algorithmus: Lade Pakete auf den Wagen, bis die Last überschritten wird, dann fahre am nächsten Tag weiter. Je größer die Tragfähigkeit, desto weniger Tage werden benötigt, also ist das Prädikat monoton.
• Die Gesamtkomplexität ist O(n · log(sum)), anstatt jede Tragfähigkeit zu versuchen.

6

Mit einer Tragfähigkeit von 6 ist der Lieferplan [3, 2], [2, 4], [1, 4], genau 3 Tage. Mit einer Tragfähigkeit von 5 benötigt man 4 Tage, also ist 5 unzureichend.

Mit diesem gleichen Schema löst man viele andere Probleme: minimale Anzahl von Threads, um Batches rechtzeitig zu verarbeiten, niedrigster Rate-Limit-Schwellwert, ganzzahlige Quadratwurzel einer Zahl.

6. Standardbibliothek von Java verwenden

Java hat bereits Arrays.binarySearch und Collections.binarySearch. Du musst den Rückgabewert verstehen:

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Arrays.binarySearch(prices, 350));
System.out.println(Arrays.binarySearch(prices, 300));

4
-5

• Wenn der Wert gefunden wird, gibt die Funktion den Index des Elements zurück.
• Wenn nicht gefunden, gibt die Funktion -(insertionPoint) - 1 zurück. Hier ist die Einfügeposition 4, also ist das Ergebnis -5. Um die Einfügeposition zurückzubekommen, berechne -(result) - 1.
• Wenn es doppelte Elemente gibt, garantiert die Dokumentation nicht, welche Position in der Gruppe zurückgegeben wird. Wenn du die erste oder letzte Position brauchst, verwende das selbst geschriebene lowerBound/upperBound.

Bei einer Liste von Objekten übergibst du einen Comparator, der der vorhandenen Ordnung entspricht:

record Order(String id, long total) {}

List<Order> orders = List.of(
        new Order("A1", 120), new Order("B7", 300), new Order("C3", 450));
int idx = Collections.binarySearch(
        orders, new Order("?", 300), Comparator.comparingLong(Order::total));
System.out.println(idx); // 1

Hinweis: Collections.binarySearch bei LinkedList erreicht nicht O(log n), da der Zugriff über Index O(n) kostet. Verwende ArrayList oder ein Array.

7. Testen

Füge die JUnit 5- und AssertJ-Abhängigkeiten hinzu. Wenn dein Projekt spring-boot-starter-test verwendet, sind beide bereits enthalten.

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.11.0</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.26.3</version>
    <scope>test</scope>
</dependency>

Schreibe Tests für Grenzfälle. Das ist der Ort, an dem binäre Suche am ehesten fehlschlägt:

import org.junit.jupiter.api.Test;
import java.util.Random;
import java.util.stream.IntStream;
import static org.assertj.core.api.Assertions.assertThat;

class BoundsTest {

    private final int[] prices = {100, 200, 200, 200, 350, 500};

    @Test
    void lowerAndUpperBoundHandleDuplicates() {
        assertThat(Bounds.lowerBound(prices, 200)).isEqualTo(1);
        assertThat(Bounds.upperBound(prices, 200)).isEqualTo(4);
    }

    @Test
    void boundsReturnInsertionPointAtEdges() {
        assertThat(Bounds.lowerBound(prices, 50)).isZero();
        assertThat(Bounds.lowerBound(prices, 900)).isEqualTo(prices.length);
        assertThat(Bounds.lowerBound(new int[0], 1)).isZero();
    }

    @Test
    void lowerBoundMatchesLinearScan() {
        Random random = new Random(42);
        for (int round = 0; round < 1_000; round++) {
            int[] a = random.ints(random.nextInt(20), 0, 10).sorted().toArray();
            int target = random.nextInt(12) - 1;
            int expected = (int) IntStream.of(a).filter(x -> x < target).count();
            assertThat(Bounds.lowerBound(a, target)).isEqualTo(expected);
        }
    }

    @Test
    void minCapacityFindsSmallestFeasibleValue() {
        int[] weights = {3, 2, 2, 4, 1, 4};
        assertThat(ShippingPlanner.minCapacity(weights, 3)).isEqualTo(6);
        assertThat(ShippingPlanner.canShip(weights, 3, 5)).isFalse();
    }
}

Der Test lowerBoundMatchesLinearScan vergleicht mit linearem Durchsuchen auf 1.000 zufälligen Arrays, einschließlich leerer Arrays. Diese Art von Vergleichstest erkennt Off-by-One-Fehler viel besser als ein paar handgeschriebene Beispiele.

8. Häufige Fehler und wann man binäre Suche nicht verwenden sollte

Häufige Fehler:

• Intervall-Konventionen vermischen. Du initialisierst hi = n (halboffenes Intervall) aber schreibst while (lo <= hi) und setzt hi = mid - 1. Das Ergebnis ist, dass man das Array überschreitet. Wähle eine Konvention und halte dich daran.
• Unendliche Schleifen. Wenn du lo = mid zusammen mit mid = (lo + hi) / 2 schreibst, dann wenn hi = lo + 1 ist, ist mid == lo und das Intervall verengt sich nicht. Falls du wirklich lo = mid brauchst, runde auf: mid = lo + (hi - lo + 1) / 2.
• Ganzzahlüberläufe bei der Berechnung von mid oder beim Addieren in binärer Suche auf die Antwort. Verwende long für Werte, die groß werden könnten.
• Nicht-monotones Prädikat. Binäre Suche gibt immer noch eine Zahl zurück, aber die ist bedeutungslos. Beweise zuerst die Monotonie, bevor du sie anwendest.

Wann du nicht binäre Suche verwenden solltest:

• Die Daten sind unsortiert und du brauchst nur ein paar mal zu suchen. Das Sortieren kostet O(n log n), lineares Suchen kostet O(n).
• Du brauchst nur „existiert oder nicht” bei vielen Suchen. Dann gibt HashSet O(1) durchschnittlich.
• Die Daten ändern sich laufend, viel Einfügen und Löschen. Ein sortiertes Array zu halten kostet O(n) je Einfügung. Überlege dir TreeMap/TreeSet, die bereits ceilingKey, floorKey, higherKey haben, entsprechend Lower Bound und Upper Bound.
• Das Array ist winzig, nur ein paar Dutzend Elemente. Lineares Durchsuchen ist oft genauso schnell oder schneller wegen Cache, und der Code ist einfacher.

9. Fazit

Binäre Suche ist nicht nur „Element im Array finden”. Wenn du Lower Bound und Upper Bound mit halboffenem Intervall [lo, hi) beherrschst, löst du Probleme mit erstem/letztem Auftreten, Zählen von Elementen und Zählen im Bereich nur mit ein paar Zeilen. Rotiertes Array braucht einen Extra-Schritt, um die sortierte Hälfte zu bestimmen. Binäre Suche auf die Antwort erweitert die Technik auf jedes Problem mit monotonem Prädikat.

Halte dir eine einzige Intervall-Konvention, verwende >>> oder lo + (hi - lo) / 2, um Überläufe zu vermeiden, und habe immer einen Test, der mit linearem Suchen vergleicht. Diese drei Gewohnheiten eliminieren fast alle Fehler, für die binäre Suche berüchtigt ist.