In diesem Kapitel:

• Die Grundlagen für das Verständnis dieses Buchs.

• Du wirst einen ersten Suchalgorithmus programmieren (eine binäre Suche).

• Du wirst erfahren, wie man die Laufzeit eines Algorithmus mit der Landau-Notation beschreibt.

1.1  Einführung

Ein Algorithmus‌ ist eine Reihe von Anweisungen, die eine Aufgabe ausführen. Man könnte eigentlich jeden Codeschnipsel als Algorithmus bezeichnen, aber dieses Buch befasst sich mit den interessanteren Aspekten. Die Algorithmen in diesem Buch habe ich ausgewählt, weil sie schnell sind, interessante Aufgabenstellungen lösen oder beides. Hier sind einige der Highlights:

• Dieses Kapitel beschreibt die binäre Suche und führt vor, wie ein Algorithmus deinen Code beschleunigen kann. In einem der Beispiele wird die Anzahl der erforderlichen Schritte von 4 Milliarden auf nur 32 reduziert!

• Ein GPS-Empfänger verwendet Graphenalgorithmen (die in Kapitel 6, Kapitel 9 und Kapitel 10 erörtert werden), um die kürzeste Route zu einem Ziel zu berechnen.

• Du kannst die dynamische Programmierung (siehe Kapitel 11) dazu verwenden, einen Algorithmus zu schreiben, der Dame spielt.

Ich werde hierfür jeweils einen Algorithmus erläutern und ein Beispiel dafür zeigen. Anschließend betrachten wir die Laufzeit des Algorithmus mithilfe der Landau-Notation (Landau-Symbole). Und schließlich erfährst du, welche anderen Aufgabenstellungen mit demselben Algorithmus gelöst werden können.

1.2  Binäre Suche

Nehmen wir an, du suchst in einem Telefonbuch nach einer Person (wie altmodisch das klingt!). Der Name beginnt mit K. Du könntest nun am Anfang des Telefonbuchs loslegen und so lange blättern, bis du zum Buchstaben K gelangst. Wahrscheinlich wirst du mit der Suche jedoch eher in der Mitte anfangen, weil du weißt, dass sich die Einträge mit K ungefähr in der Mitte des Telefonbuchs befinden.

Oder du stellst dir vor, dass du einen Begriff, der mit dem Buchstaben O beginnt, in einem Wörterbuch suchst. Auch in diesem Fall wirst du mit der Suche in der Nähe der Mitte beginnen.

Und nun stelle dir vor, dass du dich bei Facebook anmeldest. Facebook muss dann überprüfen, ob du ein Konto besitzt und dementsprechend in einer Datenbank nach deinem Namen suchen. Nehmen wir an, dein Username lautet karlmageddon. Facebook könnte nun beim Buchstaben A mit der Suche anfangen – allerdings ist es sinnvoller, irgendwo in der Mitte anzufangen.

Bei dieser Aufgabe handelt es sich um eine Suche. Zur Lösung solcher Aufgaben kommt stets der gleiche Algorithmus zum Einsatz: die binäre Suche.‌‌

Die binäre Suche ist ein Algorithmus, dessen Eingabe aus einer sortierten Liste von Elementen besteht. (Ich erkläre später, warum die Liste sortiert sein muss.) Wenn das gesuchte Element in dieser Liste enthalten ist, liefert die binäre Suche die Position zurück, an der es sich befindet. Andernfalls gibt die binäre Suche den Wert null zurück.

Zum Beispiel:

Hier ist ein Beispiel für die Funktionsweise der binären Suche. Ich denke an eine Zahl zwischen 1 und 100.

Du musst nun meine Zahl mit möglichst wenigen Versuchen erraten. Ich sage dir jeweils, ob die geratene Zahl zu groß, zu klein oder richtig ist.

Nehmen wir an, du nennst die Zahlen der Reihe nach: 1, 2, 3, 4, ... Das sähe dann folgendermaßen aus:

Hierbei handelt es sich um eine einfache Suche‌‌ (vielleicht wäre eintönige Suche in diesem Fall eine passendere Bezeichnung). Mit jedem Versuch schließt du nur eine einzige Zahl aus. Wenn ich an die Zahl 99 gedacht hätte, würdest du 99 Versuche benötigen, um meine Zahl zu erraten!