Teilen und Herrschen
In der Einführungsphase hast du die gefälschte Goldmünze gesucht. Die naive Lösung wog paarweise, die gute halbierte den Stapel. Aus vier Wägungen wurden drei – und bei 1024 Münzen aus 512 nur zehn.
Dahinter steckt eine der wichtigsten Problemlösestrategien der Informatik.
Die Strategie
Teilen und Herrschen (englisch divide and conquer) löst ein Problem in drei Schritten:
- Teilen: Zerlege das Problem in kleinere Teilprobleme derselben Art.
- Herrschen: Löse die Teilprobleme – meist rekursiv, bis sie klein genug für eine direkte Lösung sind.
- Zusammenfügen: Setze die Teillösungen zur Gesamtlösung zusammen.
Der Unterschied zur Modularisierung, die du aus der Einführungsphase kennst:
- Modularisierung zerlegt ein Problem in verschiedenartige Teilaufgaben („zeichne den Stamm“, „zeichne die Krone“).
- Teilen und Herrschen zerlegt es in gleichartige, kleinere Teilprobleme – deshalb passt Rekursion dazu so gut.
Die binäre Suche
Das einfachste Beispiel: Suchen in einem sortierten Feld.
Ein sortiertes Feld enthält die Zahlen 1 3 4 7 9 12 15 18 21 25.
Gesucht ist die 12. Gehe auf Papier so vor:
- Schau in die Mitte.
- Ist der Wert dort größer als der gesuchte, suche links weiter, sonst rechts.
- Wiederhole.
Wie viele Vergleiche brauchst du? Und wie viele bräuchte die lineare Suche?
Auflösung
| Schritt | Bereich | Mitte | Vergleich |
|---|---|---|---|
| 1 | 0 bis 9 | Index 4, Wert 9 | 9 < 12, also rechts weiter |
| 2 | 5 bis 9 | Index 7, Wert 18 | 18 > 12, also links weiter |
| 3 | 5 bis 6 | Index 5, Wert 12 | gefunden |
Drei Vergleiche. Die lineare Suche hätte sechs gebraucht.
Der Unterschied wirkt klein – bei 10 Einträgen ist er das auch. Bei einer Million Einträgen braucht die lineare Suche im Schnitt 500 000 Vergleiche, die binäre 20.
Die Umsetzung
Die binäre Suche gibt es in beiden Bauformen:
- iterativ mit einer
while-Schleife und zwei Grenzen, - rekursiv mit den Grenzen als Parametern.
Beide machen genau dieselben Vergleiche. Die rekursive Fassung zeigt die Strategie deutlicher, die iterative kommt ohne Aufrufstapel aus.
Voraussetzung ist immer, dass das Feld sortiert ist. Ohne diese Voraussetzung liefert das Verfahren falsche Ergebnisse – und zwar lautlos.
Wie schnell ist das?
Bei jedem Schritt halbiert sich der Suchbereich.
a) Wie oft kann man 1000 halbieren, bis nur noch ein Element übrig ist?
b) Wie oft bei einer Million?
c) Welche Wachstumsklasse ist das? Was passiert, wenn sich die Feldgröße verdoppelt?
Auflösung
a) 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. Das sind 10 Schritte.
b) Bei einer Million etwa 20.
c) Es ist logarithmisches Wachstum. Verdoppelt sich die Feldgröße, kommt genau ein Schritt dazu.
| n | lineare Suche | binäre Suche |
|---|---|---|
| 1 000 | 1 000 | 10 |
| 1 000 000 | 1 000 000 | 20 |
| 1 000 000 000 | 1 000 000 000 | 30 |
Das ist der dramatischste Unterschied, den du in diesem Lernpfad siehst. Und er kostet nichts außer der Bedingung, dass die Daten sortiert vorliegen.
Aufgabe 1: Selbst implementieren
Ergänze beide Fassungen so, dass alle Tests grün werden.
Tipp 1: Die Mitte
int mitte = (pLinks + pRechts) / 2;
Bei der Ganzzahldivision fällt der Rest weg – das ist genau richtig, denn ein Index muss ganzzahlig sein.
Tipp 2: Die neuen Grenzen
Nach einem Vergleich schließt man die Mitte mit aus – sie wurde ja gerade geprüft:
- Ist der Wert in der Mitte zu klein, geht es bei
mitte + 1weiter. - Ist er zu groß, geht es bis
mitte - 1.
Vergisst man das Plus bzw. Minus eins, entsteht eine Endlosschleife.
Tipp 3: Der Abbruch
Iterativ: while (links <= rechts). Sobald sich die Grenzen überkreuzen, ist der Bereich leer.
Rekursiv: if (pLinks > pRechts) return -1; – das ist der Basisfall.
Aufgabe 2: Messen
Vergleiche lineare und binäre Suche experimentell.
a) Erzeuge sortierte Felder der Größen 1000, 10 000, 100 000 und 1 000 000.
b) Suche in jedem nach einem Wert, der nicht enthalten ist – das ist der schlechteste Fall für beide Verfahren.
c) Trage die Vergleichszahlen in eine Tabelle ein. Wie verhält sich jede der beiden Reihen?
d) Beurteile: Ab welcher Feldgröße lohnt sich der Aufwand, die Daten vorher zu sortieren?
Auflösung zu c) und d)
c) Die lineare Reihe verzehnfacht sich bei jeder Zeile – sie wächst linear mit n. Die binäre Reihe steigt um jeweils etwa 3 bis 4 – sie wächst logarithmisch.
d) Sortieren kostet mit den Verfahren der Einführungsphase quadratischen Aufwand. Für eine einzige Suche lohnt sich das nie.
Der Punkt ist: Man sortiert einmal und sucht dann oft. Genau so arbeitet jede Datenbank und jedes Telefonbuch. Ab etwa zehn Suchvorgängen in einem größeren Datenbestand rechnet sich das Sortieren – und ab da immer deutlicher.
Zusatzaufgabe
Das Zahlenratespiel aus der Einführungsphase – jetzt umgekehrt: Du denkst dir eine Zahl zwischen 1 und 1000, und der Rechner rät.
a) Schreibe das Programm. Nach jedem Rateversuch fragt es, ob die Zahl zu klein, zu groß oder richtig ist.
b) Wie viele Versuche braucht es im schlechtesten Fall? Rechne es vorher aus und prüfe es dann.
c) Was passiert, wenn du zwischendurch schummelst und eine falsche Antwort gibst? Was sollte das Programm dann melden?