Suchalgorithmus

Wenn du in deinem Handy einen Kontakt suchst, willst du nicht jede Nummer einzeln lesen. Auch ein Spiel muss schnell finden, wo der nächste freie Weg liegt. Computer lösen solche Aufgaben mit festen Suchregeln. So sparen sie Zeit und vermeiden Durcheinander.

Deine Lernziele

• Du verstehst, wie Computer gezielt etwas finden.
• Du erkennst, warum die Ordnung von Daten wichtig sein kann.
• Du vergleichst einfache Suchwege miteinander.
• Du schätzt ein, warum manche Suchwege bei vielen Daten schneller sind.
• Du verstehst, wie eine gute Vermutung eine Suche lenken kann.

Wozu braucht man Suchalgorithmen?

Ein Computer hat oft sehr viele Daten vor sich: Namen, Dateien, Zahlen, Webseiten oder Spielzustände. Wenn er etwas Bestimmtes finden soll, braucht er eine klare Vorgehensweise.

Ein Algorithmus ist eine genaue Schritt-für-Schritt-Anleitung, die ein Computer ausführen kann. Ein Suchalgorithmus ist ein Algorithmus, der in einer Datenmenge ein gesuchtes Element oder eine passende Lösung findet.

Beispiel

Du suchst in einer Klassenliste den Namen "Mina".

Ein einfacher Suchalgorithmus könnte so vorgehen:

1. Lies den ersten Namen.
2. Vergleiche ihn mit "Mina".
3. Wenn er passt, stoppe.
4. Wenn er nicht passt, gehe zum nächsten Namen.
5. Wiederhole das, bis "Mina" gefunden wurde oder die Liste zu Ende ist.

Ein Suchschlüssel ist der Wert, nach dem gesucht wird. Das kann ein Name, eine Zahl, eine ID oder ein Wort sein. In einer Postleitzahlenliste kann die Postleitzahl der Suchschlüssel sein. In einer Kontaktliste kann der Name der Suchschlüssel sein.

Merke

Ein Suchalgorithmus beantwortet die Frage: Mit welchen Schritten finde ich den gesuchten Wert zuverlässig und möglichst schnell?

Lineare Suche: Schritt für Schritt durchgehen

Stell dir vor, du suchst in einem unsortierten Stapel Karteikarten eine bestimmte Karte. Du weißt nicht, ob sie vorne, hinten oder in der Mitte liegt. Dann bleibt dir oft nur: Karte ansehen, vergleichen, nächste Karte ansehen.

Die lineare Suche prüft die Elemente der Reihe nach. Linear bedeutet hier: nacheinander auf einer Linie. Der Algorithmus startet am Anfang und vergleicht jedes Element mit dem Suchschlüssel.

Beispiel

Liste: 14, 3, 9, 21, 7
Gesucht: 21

Die lineare Suche prüft:

14 ist nicht 21.
3 ist nicht 21.
9 ist nicht 21.
21 passt. Die Suche stoppt.

Es wurden 4 Elemente geprüft.

Die lineare Suche funktioniert auch, wenn die Liste nicht sortiert ist. Das ist ihr großer Vorteil. Ihr Nachteil: Bei vielen Daten kann sie langsam werden, besonders wenn das gesuchte Element weit hinten steht oder gar nicht vorkommt.

Merke

Lineare Suche ist einfach und robust. Sie passt gut zu kleinen oder unsortierten Datenmengen.

Binäre Suche: immer halbieren

Manchmal ist eine Liste schon sortiert. Dann musst du nicht jedes Element einzeln prüfen. Du kannst viel klüger vorgehen.

Die binäre Suche ist ein Suchalgorithmus für sortierte Listen. Binär bedeutet hier: Die Suche teilt den Suchbereich immer in zwei Teile. Der Algorithmus schaut in die Mitte. Dann entscheidet er, ob links oder rechts weitergesucht werden muss.

Definition

Die binäre Suche sucht in einer sortierten Liste, indem sie wiederholt das mittlere Element prüft und danach eine Hälfte der Liste ausschließt.

Beispiel

Sortierte Liste: 2, 5, 8, 12, 16, 23, 38, 56, 72
Gesucht: 23

1. Mitte prüfen: 16
   23 ist größer als 16. Also liegt 23 rechts.

2. Neuer Bereich: 23, 38, 56, 72
   Mitte prüfen: 38
   23 ist kleiner als 38. Also liegt 23 links.

3. Neuer Bereich: 23
   23 passt. Gefunden.

Wichtig ist die Voraussetzung: Die Daten müssen sortiert sein. Wenn die Liste durcheinander ist, kann die binäre Suche falsche Bereiche ausschließen.

Gut zu wissen

Eine Telefonnummernsuche im alphabetischen Adressbuch funktioniert ähnlich. Du würdest bei "Müller" nicht mit "A" anfangen und jeden Namen lesen. Du springst ungefähr in die Mitte und grenzt den Bereich ein.

Merke

Binäre Suche ist schnell, aber sie braucht sortierte Daten.

Laufzeit: Wie schnell wächst der Aufwand?

Bei kleinen Listen ist fast jede Suche schnell genug. Spannend wird es, wenn die Datenmenge wächst. Dann zählt, wie viele Vergleiche ein Algorithmus ungefähr braucht.

Die Laufzeit beschreibt, wie stark der Aufwand eines Algorithmus mit der Eingabegröße wächst. Die Eingabegröße ist hier die Anzahl der Elemente, oft mit \(n\) bezeichnet.

Definition

Die Big-O-Notation beschreibt grob, wie schnell der Aufwand eines Algorithmus wächst, wenn die Datenmenge größer wird.

Bei der linearen Suche ist die typische Laufzeit \(O(n)\). Das bedeutet: Wenn die Liste doppelt so lang wird, kann die Suche ungefähr doppelt so viele Vergleiche brauchen.

Bei der binären Suche ist die Laufzeit \(O(\log n)\). Das bedeutet: Der Aufwand wächst viel langsamer, weil der Suchbereich immer halbiert wird.

Beispiel

Du hast 1 000 sortierte Zahlen.

Lineare Suche: Im ungünstigen Fall prüfst du bis zu 1 000 Zahlen.
Binäre Suche: Du halbierst immer weiter. Nach ungefähr 10 Schritten ist der Bereich so klein, dass du das Ergebnis kennst.

Das ist der Grund, warum binäre Suche bei großen sortierten Listen so stark ist.

Merke

Big O sagt nicht die genaue Zeit in Sekunden. Es zeigt, wie der Aufwand mit mehr Daten wächst.

Suchräume, Bäume und Graphen

Nicht jede Suche läuft in einer einfachen Liste. Ein Spiel, ein Stadtplan oder ein Labyrinth besteht aus vielen möglichen Situationen und Wegen. Dafür denkt man oft in Suchräumen.

Ein Suchraum ist die Menge aller Möglichkeiten, die ein Algorithmus betrachten kann. Ein Zustand ist eine konkrete Situation in diesem Suchraum. Eine Aktion ist ein Schritt, der von einem Zustand zu einem anderen führt. Das Ziel ist der Zustand, den die Suche erreichen soll.

Beispiel

Ein Roboter steht in einem Labyrinth.

Zustand: Der Roboter steht an Feld A.
Aktionen: Er kann nach oben, rechts, unten oder links gehen.
Ziel: Er soll den Ausgang erreichen.

Der Suchalgorithmus prüft mögliche Wege, bis er einen Weg zum Ziel findet.

Merke

Suchraum, Zustand, Aktion und Ziel helfen dir, eine Suche als Weg durch Möglichkeiten zu sehen.

Ein Baum ist eine Datenstruktur mit Knoten und Verbindungen. Ein Knoten ist ein einzelner Punkt mit Daten. Die Wurzel ist der oberste Startknoten. Ein Blatt ist ein Knoten ohne weitere Nachfolger.

Beispiel

In einem Entscheidungsbaum für ein Ratespiel könnte die Wurzel die erste Frage sein:

Ist die Zahl größer als 50?
Ja führt zu einem rechten Teilbaum.
Nein führt zu einem linken Teilbaum.

So wird der Suchraum kleiner.

Ein Graph ist eine Struktur aus Knoten und Verbindungen, bei der es auch Kreise geben kann. Stadtpläne, Netzwerke und Spielkarten lassen sich oft als Graph darstellen.

Heuristische Suche: mit guter Vermutung schneller werden

Manchmal ist der Suchraum riesig. Dann wäre es zu teuer, jede Möglichkeit vollständig zu prüfen. In solchen Fällen helfen gute Schätzungen.

Eine Heuristik ist eine Faustregel oder Schätzung, die eine Suche lenkt. Sie garantiert nicht immer den perfekten Weg. Sie kann aber helfen, schneller gute Kandidaten zu prüfen.

Definition

Eine heuristische Suche nutzt Zusatzwissen über das Problem, um vielversprechende Wege früher zu untersuchen.

Beispiel

Du suchst in einer Stadt den Weg zum Bahnhof.

Ohne Heuristik könntest du jede Straße in alle Richtungen ausprobieren.
Mit Heuristik gehst du eher in die Richtung, in der der Bahnhof liegt.

Das ist nicht immer perfekt. Eine Baustelle kann den direkten Weg blockieren. Trotzdem ist die Richtung oft ein nützlicher Hinweis.

In der Informatik wird heuristische Suche zum Beispiel bei Routenplanung, Spielen, Robotern und künstlicher Intelligenz genutzt. Ein Algorithmus kann dabei bewerten, welcher nächste Schritt wahrscheinlich näher ans Ziel führt.

Gut zu wissen

Eine Heuristik ist besonders nützlich, wenn eine vollständige Suche zu lange dauern würde. Sie ist aber nur so gut wie die Schätzung, auf der sie beruht.

Zusammenfassung

Ein Suchalgorithmus ist eine klare Schrittfolge, um ein Element oder eine Lösung zu finden. Der Suchschlüssel ist der Wert, mit dem verglichen wird.

Die lineare Suche prüft Elemente nacheinander. Sie ist einfach und funktioniert auch bei unsortierten Listen. Dafür kann sie bei großen Datenmengen viele Vergleiche brauchen.

Die binäre Suche halbiert den Suchbereich immer wieder. Sie ist sehr schnell, braucht aber sortierte Daten.

Die Laufzeit beschreibt, wie der Aufwand mit der Datenmenge wächst. Mit Big O vergleichst du dieses Wachstum grob: Lineare Suche hat oft \(O(n)\), binäre Suche \(O(\log n)\).

Bei großen Suchräumen wie Bäumen, Graphen, Labyrinthen oder Spielen kann eine Heuristik helfen. Sie nutzt eine Schätzung, damit vielversprechende Wege früher geprüft werden.