Binäre Suche

Die Grundidee

Wir gehen davon aus, dass die Liste mit den Datenobjekten aufsteigend sortiert ist.

Bei der binären Suche wird der zu durchsuchende (Index-) Bereich markiert. In den Abbildungen ist es der Bereich vom hellen zum dunklen Pfeil.

Fall 1: Das Datenobjekt kommt in der Liste vor.

Fall 2: Das Datenobjekt kommt nicht in der Liste vor.

Aufgabe 1

Erläutere die Vorgehensweise und die Zusammenhänge bei der binären Suche anhand der Abbildungen. Gehe dabei auch auf folgende Fragen ein.

(a) Welches Element wird hier jeweils ausgewählt und mit dem vorgegebenen Datenobjekt verglichen?

(b) Wie wird der (Index-) Bereich in jedem Schritt angepasst?

(c) Wie erkennt man, wenn das wird vorgegebene Datenobjekt nicht in der Liste vorkommt?

(d) Verdeutliche die Vorgehensweise anhand dieser Zahlenliste: L = [4, 12, 15, 15, 21, 27, 40, 41, 70, 75, 75, 99]. Betrachte die beiden Fälle, dass das zu suchende Datenobjekt den Wert d = 75 bzw. d = 76 hat.

Ablaufmodellierung

Die Idee des Suchverfahrens lässt sich wie folgt beschreiben: Man vergleicht jeweils das vorgegebene Datenobjekt mit dem Listenelement in der Mitte des markierten Indexbereichs. Wenn man nicht fündig wird, kann man den markierten Indexbereich direkt halbieren und in dem verkleinerten Bereich analog vorgehen - bis das entsprechende Datenobjekt in der Liste gefunden ist oder der markierte Indexbereich komplett leer ist.

Der Ablauf lässt sich so präzisieren:

ALGORITHMUS binsuche
Übergabe: Datenobjekt d; Liste L
setze indexErgebnis auf -1
setze gefunden auf False
setze die linke Grenze auf die Indexzahl 0
setze die rechte Grenze auf die maximale Indexzahl der Liste
# linke und rechte Grenze ergeben den markierten Indexbereich
SOLANGE das Datenobjekt nicht gefunden ist und 
        die rechte Grenze nicht links von der linken Grenze liegt:
    bestimme die Mitte zwischen linker und rechter Grenze
    WENN das Datenobjekt mit dem Listenelement in der Mitte übereinstimmt:
        setze gefunden auf True
        setze indexErgebnis auf die Mitte
    SONST:
        WENN das Datenobjekt kleiner als das Listenelement in der Mitte ist:
            setze die rechte Grenze direkt links neben die Mitte
        SONST:
            setze die linke Grenze direkt rechts neben die Mitte
Rückgabe: indexErgebnis

Aufgabe 2

Implementiere den Algorithmus binsuche und teste das entwickelte Programm.