UniProMax/Algorithmen/binaere-suche

Binäre Suche

Halbiere den Suchraum bei jedem Schritt. O(log n) statt O(n): bei einer Milliarde Einträgen reichen 30 Vergleiche. Voraussetzung: sortiertes Array.

3LerneinheitenVoraussetzungen:Lineare Suche Mergesort

Relevant für:Informatik(Klausurniveau)Wirtschaftsinformatik(Grundlagen)Data Science(Grundlagen)

Sprache wählen

Sprache

Lerneinheit 1 von 3java + python

Binäre Suche

Der schlauere Suchalgorithmus. Nutzt aus, dass das Array sortiert ist, um den Suchraum bei jedem Schritt zu halbieren.

Die Idee

Stell dir vor, du suchst eine Seite in einem Wörterbuch:

Du schlägst nicht Seite 1 auf und blätterst durch. Du schlägst in der Mitte auf, schaust ob das gesuchte Wort davor oder dahinter steht, und wiederholst das Halbieren.

Das ist binäre Suche. Bei jeder Halbierung verringert sich die Suchmenge um 50%, daher die Komplexität $O(\log n)$ .

Voraussetzung: sortiert

Binäre Suche funktioniert nur auf sortierten Arrays. Ist das Array unsortiert, musst du es erst sortieren (kostet $O(n \log n)$ ), oder linear suchen.

Implementierung

java// snippet

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

Java: lo/hi markieren den aktuellen Suchbereich. mid wird halbiert berechnet (lo + (hi-lo)/2 statt (lo+hi)/2 zur Vermeidung von Integer-Overflow).

Komplexität

Bei jeder Iteration halbiert sich der Suchraum:

$n \to \frac{n}{2} \to \frac{n}{4} \to \frac{n}{8} \to \dots \to 1$

Wie oft kann man $n$ halbieren bis man bei 1 ankommt? $\log_2 n$ Mal.

n	Maximale Vergleiche (log₂ n)
16	4
1.024	10
1.000.000	20
1 Mrd.	30

Bei einer Milliarde Einträgen reichen 30 Vergleiche, das ist die Magie von $O(\log n)$ .

Eigenschaften

✅ Brutal effizient: O(log n) ist fast wie O(1) in der Praxis
✅ Skaliert auch bei Millionen: 30 Vergleiche reichen bei 1 Mrd. Elementen
❌ Verlangt sortiertes Array: einmaliges Sortieren kostet O(n log n)
❌ Nicht für verkettete Listen: braucht Random-Access in O(1)

Wann sinnvoll?

Bei großen sortierten Arrays: hier ist binäre Suche ungeschlagen
Bei vielen Suchanfragen: einmal sortieren, dann beliebig oft binär suchen
Bei Datenbank-Indizes: B-Bäume nutzen binäre Suche pro Knoten

Java hat Arrays.binarySearch() und Collections.binarySearch() direkt eingebaut. Python's bisect Modul bietet das gleiche.

VorkenntnisLineare Suche Baut darauf aufSuch-Vergleich