Algorithmen und Datenstrukturen in C/ Binäre Suche

Informationen

Die Binäre Suche ist ein recht schnelles Suchverfahren und hat, in der Landau-Notation(Big O Notation), ausgedrückt eine Laufzeit von O(log n). Der Algorithmus macht sich das "divide and conquer"-Prinzip zunutze. Auf Deutsch bedeutet dies so viel wie "teile und herrsche".

Vorstellung

Um die Binäre Suche etwas zu veranschaulichen stellen wir uns einfach mal ein Wörterbuch oder Telefonbuch vor. Stellen Sie sich jetzt also vor, wie Sie möglichst effizient an die gewünschte Stelle kommen: Wahrscheinlich würden Sie das Buch in der Mitte aufschlagen und dann überprüfen, ob Sie schon das Wort bzw. die Nummer zufällig aufgeschlagen haben. Falls dies nicht der Fall ist, müssen Sie vorwärts oder rückwärts blättern? Diesen letzten Schritt führen Sie dann solange aus, bis Sie am Ziel sind oder Sie zu dem Schluss kommen, dass dieses Buch unvollständig ist. Probieren Sie mit diesen Informationen einmal selbst dieses Verfahren zu implementieren.

Implementierung

Bei der Binären Suche ist anzumerken, dass die zu durchsuchende Liste sortiert vorliegen muss. Eine Beispielimplementierung würde etwa so aussehen:

int binsearch (int feld[], int links, int rechts, int wert) {
    if (links > rechts) {
        return -1;
    }
    int mitte = (rechts+links)/2;
    if (feld[mitte] == wert) {
        return mitte;
    }
    if (wert < feld[mitte]) {
        return binsearch(feld, links, mitte - 1, wert);
    } else {
        return binsearch(feld, mitte + 1, rechts, wert);
    }
}

Parameter

Es werden 4 Parameter benötigt:
Der gesuchte Wert = wert
Das Feld, das durchsucht werden soll = Feld
und die beiden Seiten rechts und links