Arbeitsblatt Suchalgorithmen II
Lösung geprüft
Die Aufgabe der heutigen Stunde ist das Arbeitsblatt zu Suchalgorithmen II! Dieselben Fragen wie beim ersten Arbeitsblatt, aber das Array ist diesmal sortiert – und damit ändert sich die Antwort komplett.
1 Einzelarbeit: In Material 1 finden Sie ein Array,
in welchem die Zahl 64 gesucht wird.
a) Begründen Sie, welches Suchverfahren Sie verwenden würden und wie
dieses vorgeht.
b) Nutzen Sie das von Ihnen gewählte Suchverfahren und führen Sie es
Schritt-für-Schritt durch. Nutzen Sie hierfür die Vorlage in
Material 2.
2 Einzelarbeit: Nun wird die Zahl 63 im Array gesucht. Beschreiben Sie, wie die binäre Suche hier vorgehen würde.
Material 1 – das sortierte Array
| Index | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Inhalt | 3 | 4 | 8 | 9 | 18 | 25 | 37 | 55 | 64 | 89 | 130 |
1 a) Welches Verfahren und warum
Diesmal ist es die binäre Suche, und der Grund ist genau der Unterschied zum ersten Arbeitsblatt: das Array ist sortiert. 3, 4, 8, 9, 18, 25 … jeder Wert ist größer als sein Vorgänger.
Erst dadurch wird der entscheidende Schluss erlaubt: ist das Element in der Mitte kleiner als der gesuchte Wert, kann der gesuchte Wert unmöglich links davon stehen. Die ganze linke Hälfte fällt mit einem einzigen Vergleich weg.
Wie sie vorgeht: Man merkt sich einen Suchbereich mit
links und rechts. In jedem Durchlauf schaut man
in dessen Mitte. Passt der Wert, ist man fertig. Ist er zu klein, geht es
rechts weiter (links = mitte + 1), ist er zu groß, links
(rechts = mitte - 1). Das wiederholt sich, solange
links <= rechts gilt.
Die lineare Suche würde hier natürlich auch funktionieren – sie ist nur unnötig langsam. Wenn die Daten sortiert sind, verschenkt man mit ihr Information, die man geschenkt bekommen hat.
1 b) Schritt für Schritt nach der 64
| Durchlauf | links | mitte | rechts | a[mitte] | Vergleich |
|---|---|---|---|---|---|
| 1 | 0 | 5 | 10 | 25 | 25 < 64 → links = 6 |
| 2 | 6 | 8 | 10 | 64 | gefunden bei Index 8 |
2 Durchläufe. Zum Vergleich: die lineare Suche hätte hier 9 gebraucht (Index 0 bis 8). Bei elf Elementen ist das noch kein Drama, bei einer Million wäre es der Unterschied zwischen sofort und gar nicht.
Zur Rechnung: mitte = (0 + 10) / 2 = 5, dann
(6 + 10) / 2 = 8. Beides geht glatt auf. Bei krummen
Ergebnissen schneidet die int-Division einfach ab – aus 3,5
wird 3.
2 – Die Suche nach der 63
| Durchlauf | links | mitte | rechts | a[mitte] | Vergleich |
|---|---|---|---|---|---|
| 1 | 0 | 5 | 10 | 25 | 25 < 63 → links = 6 |
| 2 | 6 | 8 | 10 | 64 | 64 > 63 → rechts = 7 |
| 3 | 6 | 6 | 7 | 37 | 37 < 63 → links = 7 |
| 4 | 7 | 7 | 7 | 55 | 55 < 63 → links = 8 |
| – | 8 | links (8) > rechts (7) → Bereich leer, nicht gefunden | |||
Vier Durchläufe, dann bricht die Schleife ab. Interessant ist, wie sich
der Suchbereich zusammenzieht: erst 0–10, dann 6–10, dann 6–7, dann 7–7 –
und dann überholt links das rechts. In dem
Moment ist der Bereich leer und es kann nichts mehr kommen.
Die 63 müsste zwischen der 55 (Index 7) und der 64 (Index 8) stehen. Genau dorthin läuft die Suche auch, und genau dort ist kein Platz – also gibt es die 63 nicht.
Der direkte Vergleich der beiden Arbeitsblätter
| AB I – unsortiert | AB II – sortiert | |
|---|---|---|
| Mögliches Verfahren | nur linear | linear oder binär |
| Vergleiche für die 64 | 8 | 2 |
| Vergleiche für die fehlende 63 | 11 (alle) | 4 |
| Aufwand | O(n) | O(log n) |
Beide Arbeitsblätter zusammen sind eine einzige Argumentation: Sortierung kostet vorher Arbeit und spart nachher viel mehr. Wenn man ein Array einmal sortiert und danach tausendmal darin sucht, lohnt sich das sofort. Sucht man nur ein einziges Mal, kann die lineare Suche auf unsortierten Daten die bessere Wahl sein.
Und das ist auch der Übergang zum nächsten Thema: wenn Sortierung so wertvoll ist, sollte man wissen, wie man effizient sortiert.