Lineare und binäre Suche

Die Suche ist eine der grundlegendsten Operationen der Informatik: Gegeben eine Datenstruktur (z. B. ein Array) und ein Suchschlüssel, soll festgestellt werden, ob der Schlüssel vorkommt und gegebenenfalls an welcher Position. Die Wahl des Algorithmus entscheidet, ob diese Operation in Sekundenbruchteilen oder in Minuten läuft. Im Abitur werden zwei Verfahren verglichen: die lineare Suche auf beliebigen Arrays und die binäre Suche auf bereits sortierten Arrays.

Die lineare Suche durchläuft das Array von links nach rechts und vergleicht jedes Element mit dem Suchschlüssel. Sobald ein Treffer gefunden wird, gibt der Algorithmus den Index zurück; ist das Ende erreicht, gibt er einen Misserfolgswert (z. B. -1) zurück. Das Verfahren funktioniert auf unsortierten Daten und ist denkbar einfach zu implementieren.

Java-Implementierung:

public static int linearSearch(int[] a, int key) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == key) return i;
    }
    return -1;
}

Python-Implementierung:

def linear_search(a, key):
    for i, x in enumerate(a):
        if x == key:
            return i
    return -1

Die binäre Suche setzt voraus, dass das Array aufsteigend sortiert ist. Sie vergleicht den Suchschlüssel mit dem mittleren Element. Ist der Schlüssel kleiner, wird in der linken Hälfte weitergesucht, ist er größer, in der rechten Hälfte. So halbiert jeder Schritt den Suchbereich (Divide and Conquer).

Java-Implementierung:

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

Python-Implementierung:

def binary_search(a, key):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == key:
            return mid
        elif a[mid] < key:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Die lineare Suche benötigt im schlimmsten Fall \( n \) Vergleiche, die Laufzeit ist also \( \mathcal{O}(n) \). Im Mittel sind es \( n/2 \) Schritte. Bei einer Million Elementen entspricht das bis zu einer Million Vergleichen.

Die binäre Suche halbiert den Suchbereich in jedem Schritt. Nach \( k \) Schritten verbleiben \( n / 2^k \) Elemente. Der Algorithmus stoppt, wenn nur noch ein Element übrig ist, also \( k = \log_2 n \). Die Laufzeit ist \( \mathcal{O}(\log n) \). Bei einer Million Elementen sind das nur etwa 20 Vergleiche.

Die lineare Suche wird verwendet, wenn die Daten unsortiert oder sehr klein sind. Die binäre Suche kommt überall dort zum Einsatz, wo eine sortierte Reihenfolge bereits vorliegt – etwa in Datenbankindizes (B-Bäume), Wörterbüchern oder Telefonbüchern. Wer einmal sortiert und sehr oft sucht, profitiert massiv von der binären Suche.

Bei der binären Suche ist die Berechnung der Mitte gefährlich: (lo + hi) / 2 kann bei sehr großen Arrays zu einem Integer-Überlauf führen. Sicherer ist lo + (hi - lo) / 2. Außerdem werden häufig die Abbruchbedingung (lo <= hi) und die Aktualisierung der Grenzen (mid + 1, mid - 1) vertauscht – dann läuft die Schleife endlos.

Zusammenfassung: Die lineare Suche ist einfach und funktioniert überall, ist aber mit \( \mathcal{O}(n) \) langsam. Die binäre Suche ist mit \( \mathcal{O}(\log n) \) deutlich schneller, setzt jedoch sortierte Daten voraus.

Abitur-Tipp: Begründe im Abitur immer, warum die binäre Suche sortierte Daten benötigt, und rechne die Anzahl der Vergleiche für konkrete \( n \) durch (z. B. \( n=1024 \rightarrow 10 \) Schritte).