Mai 2023 › EU-Datenbank.de

Die wichtigsten Infos rund um Suchalgorithmen, 1. Teil

Der Schlüsselbund ist wie vom Erdboden verschluckt, die Lesebrille ist einfach nicht aufzufinden oder die zweite Socke ist verschollen? In solchen Fällen wäre es praktisch, nicht selbst die ganze Wohnung durchsuchen zu müssen, sondern sich einfach anzeigen lassen zu können, wo der vermisste Gegenstand steckt. Im realen Leben klappt das so leider (noch) nicht.

Die wichtigsten Infos rund um Suchalgorithmen, 1. Teil

Bei Daten auf dem Computer oder Laptop sieht die Sache anders aus. Hier können Suchalgorithmen nämlich die rettende Lösung sein.

Doch wie funktionieren Suchalgorithmen eigentlich? In welchen Varianten gibt es sie? Und wodurch unterscheiden sie sich voneinander?

Wir vermitteln die wichtigsten Infos rund um Suchalgorithmen!:

Was genau sind Suchalgorithmen überhaupt?

Bei einem Suchalgorithmus handelt es sich um ein Verfahren, das Schritt für Schritt Daten innerhalb einer Datensammlung ausfindig macht. Die Aufgabe und wesentliche Funktion eines Suchalgorithmus besteht also darin, aus einer Datenmenge bestimmte Daten herauszufiltern.

Die Funktionsweise hängt dabei vom Verfahren ab. Generell lassen sich Suchalgorithmen in einfache und heuristische Verfahren unterscheiden. Heuristische Algorithmen beachten präzisere Informationen über die Datenmenge, die sie durchsuchen.

In der Informatik gehören Suchalgorithmen zu den grundlegenden Verfahren. Ein wesentlicher Faktor ist die Schnelligkeit. Das Ziel ist, die Laufzeit möglichst kurzzuhalten.

Der Algorithmus soll die gesuchten Daten also möglichst schnell finden. Ein weiteres Unterscheidungsmerkmal ist die Art, wie Suchalgorithmen in ein System eingebunden werden können.

Welche Arten von Suchalgorithmen gibt es?

Wie der Name schon nahelegt, werden Suchalgorithmen eingesetzt, um einzelne Daten, Listen oder Baumstrukturen zu durchsuchen. Je nachdem, welche Anforderungen bestehen und welche Bedingungen erfüllt sein sollen, kommen verschiedene Arten von Suchalgorithmen zum Einsatz.

Die drei wesentlichen Kategorien dabei sind einfache Suchalgorithmen, heuristische Suchalgorithmen und weitere Suchverfahren.

Einfache Suchalgorithmen

Zu den einfachen Suchalgorithmen gehört zum Beispiel die Suche in Listen oder in Bäumen. Einer ihrer Pluspunkte ist, dass einfache Suchalgorithmen in den meisten Fällen abstrakter programmiert werden können.

Außerdem können sie bei einer Vielzahl unterschiedlicher Probleme angewendet werden.

Ein Minuspunkt ist aber, dass solche Algorithmen oft vergleichsweise lange Laufzeiten haben. Die langsame Suche senkt die Effizienz und führt zudem zu einem eher schlechten Kosten-Nutzen-Verhältnis.

Heuristische Suchalgorithmen

Im Unterschied zu den einfachen Suchalgorithmen nutzen heuristische Algorithmen mehr und detailliertere Informationen über die Datenmenge, die sich durchsuchen. So berücksichtigen die Verfahren zum Beispiel, wie die Daten verteilt sind.

Grundsätzlich werden heuristische Suchalgorithmen hauptsächlich dann angewendet, wenn ein Suchverfahren in seiner Komplexität und der benötigten Rechenleistung reduziert werden soll.

Eine Heuristik beschreibt in diesem Zusammenhang eine Vorgehensweise, die schneller zu Lösungsstrategien für ein Problem führt.

Heuristische Suchalgorithmen lassen sich dabei in informierte und uninformierte Algorithmen unterscheiden:

Ein informierter Algorithmus durchläuft zuerst die Knoten in einem Datenbaum, die am vielversprechendsten sind. Dafür braucht der Algorithmus natürlich entsprechende Zusatzinformationen, damit er die Knotenpunkte kennt, an denen er seine Suche starten sollte.
Ein uniformierter Suchalgorithmus durchläuft die Knoten in einem Datenbaum einfach nacheinander. Umgangssprachlich wird so ein Verfahren auch blinde Suche genannt.

Weitere Suchverfahren

Neben den einfachen und den heuristischen Suchalgorithmen gibt es noch eine Reihe weiterer Suchverfahren. Beispiele dafür sind die optimierende Suche und ein Suchverfahren für Zeichenketten:

Die optimierende Suche basiert auf bestimmten Variablen, die vorher definiert wurden. Bei der Suche selbst werden die Werte dann den entsprechenden Variablen zugeordnet. Eine typische Anwendung ist beispielsweise das Backtracking.
Ein Suchverfahren für eine Zeichenkette sucht innerhalb einer Zeichenkette nach einem bestimmten Schlüssel. Solche Verfahren werden den sogenannten String-Matching-Algorithmen zugeordnet.

Wie funktionieren Suchalgorithmen?

Suchalgorithmen nutzen verschiedene Vorgehensweisen, um die gesuchten Daten zu finden.

Lineare Suche

Die lineare Suche wird auch als sequentielle Suche bezeichnet und gehört zu den einfachen Suchalgorithmen. Sie wird in aller Regel bei Datenmengen angewendet, die nicht sortiert und nicht allzu groß sind.

Ein simples Beispiel für eine lineare Suche wäre, wenn in einer Datensammlung das kleinste Element gefunden werden soll.

Im Zuge der Suche müssten dann alle Daten durchlaufen und die einzelnen Elemente miteinander verglichen werden. Weil die notwendige Anzahl an Vergleichen dabei ebenfalls linear steigt, ist diese Form der Suche meist vergleichsweise langwierig.

Binäre Suche

Effektiver als die lineare Suche ist die binäre Suche. Allerdings setzt die binäre Suche voraus, dass die Datenmenge zuvor sortiert wurde. Die Vorgehensweise basiert dann auf dem sogenannten Teile-und-Herrsche-Prinzip.

Beim obigen Beispiel für die Suche nach dem kleinsten Element in einer sortierten Datensammlung würde eine binäre Suche so ablaufen:

Ein mittleres Element wird ausgewählt und mit dem gesuchten Element verglichen.
Ist das mittlere Element kleiner, wird die Suche in der rechten Hälfte fortgesetzt. Ist es größer, geht die Suche in der linken Hälfte weiter.
Die Hälfte, die jetzt die neue Datenmenge bildet, wird erneut halbiert. Anschließend wird das mittlere Element wieder mit dem gesuchten Element abgeglichen.
Dieses Prinzip wird so lange wiederholt, bis das gesuchte Element schließlich gefunden ist.

Eine modifizierte Variante der binären Suche ist die Interpolationssuche. Sie kennzeichnet sich dadurch, dass die Daten nicht exakt in der Mitte aufgeteilt werden, sondern die Größe der Teilmengen dynamisch festgelegt werden kann.

Das bringt den Vorteil mit sich, dass es möglich ist, die Teilmengen anhand des gesuchten Werts zu wählen. Bezieht sich die Suche zum Beispiel auf einen niedrigen Wert, kann die Datenmenge in einem entsprechend niedrigen Bereich aufgeteilt werden. Im Ergebnis müssen weniger Daten durchsucht werden, um den gesuchten Wert zu finden.

Mehr Ratgeber, Tipps und Anleitungen:

Thema: Die wichtigsten Infos rund um Suchalgorithmen, 1. Teil