Elementare Algorithmen

Binäre Suche

In einer sortierten Liste können Sie schneller nach einem bestimmten Element suchen als in einer unsortierten Liste.

Im Telefonbuch nach einem bestimmten Namen zu suchen, geht schnell, denn das Telefonbuch ist alphabetisch nach Namen sortiert. Im Telefonbuch nach dem Inhaber einer bestimmten Telefonnummer zu suchen, ist dagegen nahezu aussichtslos, da das Telefonbuch nicht nach Telefonnummern sortiert ist.

Das Suchverfahren, das eine schnelle Suche in sortierten Listen ermöglicht, heißt binäre Suche.

Wenn Sie beispielsweise im Telefonbuch nach dem Namen "Christiansen" suchen, schlagen Sie das Telefonbuch in der Mitte auf. Steht dort der Name "Christiansen", so sind Sie fertig. Steht dort aber beispielsweise "Lehmann", so wissen Sie, dass Sie jetzt nur noch in der vorderen Hälfte des Telefonbuchs suchen müssen, denn "Christiansen" kommt alphabetisch vor "Lehmann". In der vorderen Hälfte suchen Sie mit dem gleichen Verfahren weiter, indem Sie die vordere Hälfte in der Mitte aufschlagen usw.

Wenn Sie das Telefonbuch an einer bestimmten Stelle aufschlagen, gibt es immer drei Möglichkeiten: Entweder, Sie haben den gesuchten Namen auf der entsprechenden Seite gefunden, oder Sie müssen in der vorderen Hälfte des noch zu durchsuchenden Teils weitersuchen, oder in der hinteren Hälfte.

Diese Vorgehensweise entspricht einer besonders effizienten Anwendung der Divide-and-Conquer-Strategie. Das Problem wird in zwei Hälften, also zwei Teilprobleme zerlegt (Divide). Nur eines dieser Teilprobleme muss gelöst werden (Conquer). Damit entfällt auch das Zusammenführen der Teillösungen (Combine).

Für die Implementierung eines Divide-and-Conquer-Algorithmus bietet sich immer Rekursion an. Die folgende Implementierung sucht eine bestimmte Integer-Zahl x in einem aufsteigend sortierten Array a von Integer-Zahlen.

Die Rekursion endet sofort, wenn der zu durchsuchende Teilbereich so weit eingeengt ist, dass er leer ist; in diesem Fall kommt das Element x nicht im Array vor und es wird -1 zurückgegeben. Ansonsten wird die Mitte m des zu durchsuchenden Bereichs bestimmt und anschließend entweder in der vorderen Hälfte oder in der hinteren Hälfte nach x gesucht, je nach dem, ob x kleiner oder größer als a[m] ist. Ist weder das eine noch das andere der Fall, so ist x gleich a[m] und es wird die gefundene Position m zurückgegeben.

Die Mitte m zwischen lo und hi lässt sich einfach als Mittelwert (lo+hi)/2 von lo und hi berechnen, jedoch besteht hier die Gefahr eines Integer-Überlaufs, wenn lo+hi größer als 2.147.483.647 wird. Daher wird hier die etwas kompliziertere Berechnung lo+(hi-lo)/2 gewählt.

Wenn x mehrfach im Array a vorkommt, wird irgendeine der entsprechenden Indexpositionen zurückgegeben, also nicht unbedingt die erste.

Die Klasse BinarySearcher implementiert das Interface Searcher; dort wird die Methode search vorgeschrieben.

Binäre Suche rekursiv
public class BinarySearcher implements Searcher { // sucht das Element x in einem aufsteigend sortierten Array a // und gibt die Indexposition eines Vorkommens von x zurück // bzw. -1, falls x nicht vorkommt @Override public int search(int[] a, int x) { return binsearch(a, 0, a.length-1, x); } public int binsearch(int[] a, int lo, int hi, int x) { if (lo>hi) return -1; int m=lo+(hi-lo)/2; if (x<a[m]) return binsearch(a, lo, m-1, x); if (x>a[m]) return binsearch(a, m+1, hi, x); return m; } }

Binäre Suche rekursiv

public class BinarySearcher implements Searcher
{
    // sucht das Element x in einem aufsteigend sortierten Array a
    // und gibt die Indexposition eines Vorkommens von x zurück
    // bzw. -1, falls x nicht vorkommt
    @Override
    public int search(int[] a, int x)
    {
        return binsearch(a, 0, a.length-1, x);
    }

    public int binsearch(int[] a, int lo, int hi, int x)
    {
        if (lo>hi)
            return -1;
        int m=lo+(hi-lo)/2;
        if (x<a[m])
            return binsearch(a, lo, m-1, x);
        if (x>a[m])
            return binsearch(a, m+1, hi, x);
        return m;
    }

}

Binäre Suche lässt sich auch iterativ implementieren. In der folgenden Implementierung werden die Grenzen lo und hi des zu durchsuchenden Bereichs jeweils entsprechend angepasst, je nach dem, ob in der vorderen oder hinteren Hälfte weitergesucht werden soll.

Binäre Suche iterativ
public class BinarySearcherIterative implements Searcher { // sucht das Element x in einem aufsteigend sortierten Array a // und gibt die Indexposition eines Vorkommens von x zurück // bzw. -1, falls x nicht vorkommt @Override public int search(int[] a, int x) { return binsearch(a, 0, a.length-1, x); } public int binsearch(int[] a, int lo, int hi, int x) { while (lo<=hi) { int m=lo+(hi-lo)/2; if (x<a[m]) hi=m-1; else if (x>a[m]) lo=m+1; else return m; } return -1; } }

Binäre Suche iterativ

public class BinarySearcherIterative implements Searcher
{
    // sucht das Element x in einem aufsteigend sortierten Array a
    // und gibt die Indexposition eines Vorkommens von x zurück
    // bzw. -1, falls x nicht vorkommt
    @Override
    public int search(int[] a, int x)
    {
        return binsearch(a, 0, a.length-1, x);
    }

    public int binsearch(int[] a, int lo, int hi, int x)
    {
        while (lo<=hi)
        {
            int m=lo+(hi-lo)/2;
            if (x<a[m])
                hi=m-1;
            else if (x>a[m])
                lo=m+1;
            else
                return m;
        }
        return -1;
    }

}