Binary-Search

Geschrieben von Stefanie Zbinden und Florian Wernli.

Problemstellung

Ein häufig angetroffenes Problem ist das Auffinden bestimmter Elemente in einer Liste. Ist diese Liste sortiert kann das Element gefunden werden, ohne alle Elemente zu überprüfen.

Zum Beispiel haben wir ein Array \(a\). Die Elemente des Arrays sind aufsteigend sortiert, das heisst dass das \(a[i] \le a[i+1]\). Wir nehmen an, dass alle Elemente einmalig im Array vorkommen, nachfolgende Elemente also strikt grösser sind (\(a[i] < a[i+1]\)). Nun möchten wir die Position des Elements \(x\) im Array finden.

Lösungsidee

Vergleichen wir ein Element an der Position \(k\) mit dem gesuchten Wert \(x\) so gibt es drei Möglichkeiten: 1. Wir haben Glück und \(x=a[k]\), dann brauchen wir nicht weiter zu suchen. 2. Wahrscheinlicher ist aber, dass \(x < a[k]\) … 3. … oder \(x > a[k]\) ist.

Da wir von einem sortierten Array ausgehen, können wir sagen, dass wenn \(x > a[k]\) auch gilt, dass \(x\) grösser als alle vorhergehenden Elemente (\(a[k-1], a[k-2], ... a[0]\)) ist. Für die weitere Suche können diese Elemente im Vorherein ausgeschlossen werden. Dasselbe gilt auch in die andere Richtung, ist \(x < a[k]\) müssen alle Elemente mit einem höheren Index auch grösser als \(x\) sein und sind daher für uns uninteressant.

Konkret wird bei der Binary-Search (auch binäre Suche) der Index des Anfangs und des Ende des sortierten Suchbereichs gespeichert. Nun wird das mittlere Element für den Vergleich gewählt. Ist das gesuchte Element grösser, wird der Anfang des Suchbereichs auf dieses Element verschoben. Ist das Element kleiner, wird es als oberes Ende des neuen Suchbereichs verwendet. Dieser Vorgang wird mit dem nun noch halb so grossen Bereich wiederholt bis das Element gefunden wurde oder keine Elemente mehr im Suchbereich liegen (Anfang = Ende).

Implementation

/*
 * int[]     a     : Sortiertes Array
 * int       x     : gesuchtes Element
 * long long start : Anfang des Suchbereiches
 *                   0 falls ganzes Array durchsucht werden soll
 * long long end   : Ende des Suchbereiches
 *                   Höchstens Index des letzten Elements
 */
long long binary_search(int[] a, int x, long long start, long long end){
    while(start<=end){             //solange es noch andere Mögl. hat
        long long middle=(a+b)/2;  //Mittleres Element bestimmen
        if(a[middle]==x)           //Element x gefunden
            return middle;
        else if(x<a[middle])       //x ist kleiner
            end=middle-1;          //Ende verschieben
        else                       //x ist grösser
            start=middle+1;        //Anfang verschieben
    }
    //Im Suchbereich sind keine Elemente mehr vorhanden.
    //x ist kein Element von a[]
    return -1;
}

Speicher und Laufzeitanalyse

Wir müssen nur eine fixe Anzahl Werte speichern. Egal ob wir \(10\) oder \(1000\) Elemente haben, wir brauchen nur den oberen und unteren Rand des Bereiches sowie die Mitte zu speichern, daher ist der Speicherverbrauch \(O(1)\).

Die Laufzeit ist etwas schwieriger zu bestimmen. Kurz gesagt ist die Laufzeit \(O(k\cdot\log(n))\). Für \(k\) muss jeweils die Laufzeit der Vergleichsoperation eingetragen werden. Beim Verlgeich von elementaren/primitiven Datentypen ist \(k=1\), die Laufzeit der Binary-Search also \(O(log(n))\). Werden Strings (Zeichenketten), Listen oder Bigints verglichen ist \(k\) von deren Länge abhähngig.

Laufzeitanalyse (Weshalb log(n)?)

Jeder Vergleich halbiert den Suchbereich. Rückwärts betrachtet bedeutet dies, dass der letzte Vergleich bei einem Bereich von 2 Elementen durchgeführt wurde, der zweit letzte in einem Bereich von 4 Elementen … \(1\) Vergleich bei \(2\) Elementen \(2\) Vergleiche bei \(4\) Elementen \(3\) Vergleiche bei \(8\) Elementen \(m\) Vergleiche bei \(2^m\) Elementen Daraus ist ersichtlich, dass bei \(n\) Elementen \(\log_2(n)\) Vergleiche stattfinden.