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.