Open in App
Login Anmelden

Select your language

Suggested languages for you:
StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
|
|
Suchalgorithmen

Du hast mal wieder Dein Ladekabel verlegt oder findest die zweite Socke nicht? Wie schön wäre es in solchen Fällen nicht selbst das komplette Zimmer durchforsten zu müssen, sondern sich einfach anzeigen lassen zu können, wo sich der gesuchte Gegenstand befindet. 

Inhalt von Fachexperten überprüft
Kostenlose StudySmarter App mit über 20 Millionen Studierenden
Mockup Schule

Entdecke über 50 Millionen kostenlose Lernmaterialien in unserer App.

Suchalgorithmen

Illustration

Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken

Jetzt kostenlos anmelden

Nie wieder prokastinieren mit unseren Lernerinnerungen.

Jetzt kostenlos anmelden
Illustration

Du hast mal wieder Dein Ladekabel verlegt oder findest die zweite Socke nicht? Wie schön wäre es in solchen Fällen nicht selbst das komplette Zimmer durchforsten zu müssen, sondern sich einfach anzeigen lassen zu können, wo sich der gesuchte Gegenstand befindet.

Das ist im realen Leben natürlich nicht so einfach möglich – anders sieht es jedoch aus, wenn Du z. B. Dateien auf Deinem Computer oder Laptop suchst. In solchen Fällen können Suchalgorithmen Deine Rettung sein. Wie die funktionieren und was es für Unterschiede gibt, erfährst Du in dieser Erklärung.

Suchalgorithmen Informatik

Die wichtigste Frage zuerst: Was ist überhaupt ein Suchalgorithmus?

Ein Suchalgorithmus ist ein Verfahren, bei dem Schritt für Schritt Daten innerhalb einer Datensammlung ausfindig gemacht werden.

Suchalgorithmen gehören zu den grundlegenden Methoden in der Informatik – genau wie die Sortieralgorithmen. Bei beiden ist die Laufzeit – also die Schnelligkeit des Algorithmus – ein wichtiger Faktor. Neben der Effizienz unterscheiden sich Suchalgorithmen auch anhand ihres Aufbaus, also der Art und Weise, wie sie implementiert werden können.

Was sich mit Sortieralgorithmen alles sortieren lässt sowie mehr zu den einzelnen Verfahren und Vorgehensweisen findest Du in der gleichnamigen Erklärung auf StudySmarter.

Suchalgorithmen Anwendung

Doch wofür werden Suchalgorithmen genau angewendet? Wie es der Name bereits verrät, werden mithilfe von Suchalgorithmen Daten, Listen oder Baumstrukturen durchsucht. Wann welcher Algorithmus verwendet wird, kannst Du den folgenden Abschnitten entnehmen.

Suchalgorithmen Arten

Es existiert eine Reihe verschiedener Arten von Suchalgorithmen:

  • Einfache Suchalgorithmen

  • Heuristische Suchalgorithmen

  • Weitere Suchverfahren

In den nachfolgenden Abschnitten werden die drei Kategorien genauer beschrieben.

Einfache Suchalgorithmen

Der Hintergrund von einfachen Suchalgorithmen ist, dass sie meist abstrakter implementiert werden können. Außerdem können sie für eine Vielzahl von Problemen eingesetzt werden. Ein Nachteil ist jedoch, dass diese Algorithmen bei der Suche kein gutes Kosten-Nutzen-Verhältnis haben und meistens eine relativ lange Laufzeit besitzen.

Zu den einfachen Suchalgorithmen gehören das Suchen in Listen oder auch die Suche in Bäumen.

Heuristische Suchalgorithmen

Im Gegensatz zu den einfachen Suchalgorithmen besitzen heuristische Verfahren genauere Informationen über die zu durchsuchende Datenmenge wie z. B. über die Verteilung der Daten. Bei den heuristischen Suchalgorithmen kann zusätzlich zwischen informierten und uninformierten Suchalgorithmen unterschieden werden.

Informierte Suchalgorithmen

Die informierte Suche besucht zunächst "vielversprechende" Knoten in einem Baum. Dafür werden entsprechende Zusatzinformationen benötigt, damit der Algorithmus weiß, welche Knoten zuerst durchlaufen werden sollten.

Informierte Suchverfahren gehören zu den sogenannten "heuristischen Suchalgorithmen". Verwendet werden diese Algorithmen vor allem dann, wenn die Komplexität und die Rechenleistung eines Algorithmus verringert werden soll.

Unter einer Heuristik versteht man ein Vorgehen, mit der Lösungsstrategien für ein Problem schneller gefunden werden können.

Uninformierte Suchalgorithmen

Bei der uniformierten Suche werden Knoten in einem Baum einfach der Reihe nach durchlaufen.

Uniformierte Suchverfahren werden umgangssprachlich auch als "blinde Suche" bezeichnet.

Weitere Suchverfahren

Neben den beiden bereits genannten Kategorien gibt es noch weitere Suchverfahren, dazu gehören z. B.:

  • Optimierende Suche

  • Suchverfahren für Zeichenketten

Optimierende Suche

Bei der optimierenden Suche werden Werte bestimmten vorher definierten Variablen zugeordnet. Dazu gehört z. B. das Backtracking.

Suchverfahren für Zeichenketten

Ein Suchverfahren für eine Zeichenkette sucht innerhalb einer solchen nach einem bestimmten Schlüssel. Diese Art von Verfahren zählen zu den sogenannten "String-Matching-Algorithmen", dazu zählen z. B.:

  • Knuth-Morris-Pratt Algorithmus
  • Boyer-Moore Algorithmus
  • Karp-Rabin Algorithmus

Suchalgorithmen Beispiele

Weitere Beispiele für Suchalgorithmen findest Du in den nachfolgenden Abschnitten.

Lineare Suche

Zu den einfachen Suchalgorithmen gehört die lineare oder auch sequentielle Suche. Sie wird in der Regel bei ungeordneten Arrays verwendet und eignet sich vor allem bei eher kleineren Datenmengen.

Ein einfaches Beispiel für eine lineare Suche: Durchsuche eine Datenmenge nach dem kleinsten oder größten Element. Dabei musst Du die Daten durchgehen und alle Elemente miteinander vergleichen. Dadurch steigt die benötigte Anzahl an Vergleichen ebenfalls linear an – was die lineare Suche meist nicht besonders schnell macht.

Binäre Suche

Eine effektivere Variante ist die binäre Suche. Die Voraussetzung bei einer binären Suche ist allerdings, dass die Datenmenge vorher sortiert wurde. Bei der binären Suche wird nach dem "Teile-und-Herrsche-Prinzip" vorgegangen.

Die Vorgehensweise bei der binären Suche ist folgende:

  • Mittleres Element suchen und mit gesuchtem Element vergleichen

    • Ist es kleiner, suche in der rechten Hälfte weiter

    • Ist es größer, suche in der linken Hälfte

  • "Neue" Datenmenge erneut halbieren und das gesuchte Element mit dem mittleren Element vergleichen

  • Das ganze so lange weiter durchführen, bis das gesuchte Element gefunden wurde

Interpolationssuche

Die Interpolationssuche ist eine Modifizierung der binären Suche. Der Unterschied liegt darin, dass die Interpolationssuche Daten nicht in der Mitte unterteilt, sondern die Größe der Teilmengen dynamisch gewählt werden können.

Das hat den Vorteil, dass Du die Trennung anhand des gesuchten Wertes wählen kannst. Suchst Du z. B. einen niedrigen Wert, kannst Du die Datenmenge in einem entsprechend niedrigen Bereich trennen und musst im Zweifelsfalls weniger Daten nach Deinem gesuchten Wert durchsuchen.

Binäre (Such-)Bäume

Eine weitere Möglichkeit um zu Suchen sind binäre und nicht binäre Suchbäume. Dabei ist das Prinzip ein ähnliches: Bei Suchen in Bäumen werden die einzelnen Knoten nacheinander durchgegangen. Die Vorgehensweise ist folgende:

  • Entnehme einen Knoten aus einem Suchbaum
  • Untersuche seine Kindknoten

In welcher Reihenfolge Du einen Baum durchsuchst, hängt vor verwendeten Verfahren ab. Dabei kannst Du z. B. die Breitensuche und die Tiefensuche unterscheiden. Auch Suchbäume enthalten bereits sortierte Datensätze, die je nach Art des Baumes aufsteigend oder absteigend sortiert sein können.

Sowohl die Breitensuche (breadth-first search) als auch die Tiefensuche (depth-first search) sind Methoden, um Knoten in einem Graphen zu finden. Bei der Breitensuche werden zunächst alle Nachbarn bearbeitet, die am nächsten zum aktuellen Knoten sind. Die Tiefensuche geht stattdessen zuerst alle Kindknoten eines Knotens durch. Beide Verfahren gehören zu den uninformierten Suchalgorithmen.

Mehr Informationen erhältst Du in den Erklärungen zu "Suchbäume" und dem "Binärbaum" auf StudySmarter.

Suche in Graphen

Auch Suchen in Graphen können durch verschiedene Suchalgorithmen gelöst werden. Algorithmen, die Du dafür verwenden kannst, sind:

Zu allen drei Algorithmen findest Du jeweils eine eigenständige Erklärung auf StudySmarter.

Hash-Suche/Hash-basierte Suche

Außerdem gibt es noch die Möglichkeit, mittels Hashverfahren zu suchen. Die Idee dahinter ist mithilfe eines Schlüssels, einer Hashfunktion und einer dazugehörigen Hashadresse eine sogenannte Hashtabelle zu erzeugen. Die Hashadresse gibt dabei genau an, an welcher Stelle, bzw. in welchem Feld sich der Datensatz befindet. In einer solchen Hashtabelle ist es nun möglich, Datensätze zu suchen.

Mehr zu diesen Prinzipien kannst Du in den Erklärungen zum Datenmapping und zum Hashing auf StudySmarter nachlesen.

Suchalgorithmen Übersicht

Nachfolgend findest Du eine Übersicht verschiedener Suchverfahren und ihrer wichtigsten Vor- und Nachteile:

SuchalgorithmenVorteileNachteile
Lineare SucheEinfach zu implementieren.Dauert bei großen Datenmengen sehr lange.
Kann auch in nicht sortierten Datenmengen verwendet werden.
Sortierte Daten bleiben sortiert, auch wenn ein neues Element eingefügt wird.
Binäre SucheEignet sich auch bei etwas größeren Datenmengen.Die binäre Suche funktioniert nur in sortierten Datenmengen. Sollen neue Elemente eingefügt werden, müssen die Daten zunächst neu sortiert werden.
Eignet sich besonders gut für bereits sortierte, kleine Datensätze.
InterpolationssucheIst als Modifizierung der binären Suche schneller als diese, da durch die dynamische Wahl der Trennung meist weniger Werte durchsucht werden müssen.Funktioniert ebenfalls nur in sortierten Datenmengen.

Suchalgorithmen Vergleich

Die Kriterien zum Vergleich von Suchalgorithmen sind vergleichbar mit denen für Sortieralgorithmen. Dazu gehören z. B.:

  • Laufzeit / Komplexität

  • Zusätzlicher Speicherbedarf / Platzkomplexität

  • Stabilität

  • Intern vs. extern / in-place vs. out-of-place

  • Rekursiv vs. iterativ

Ein genauer Vergleich muss dabei immer spezifisch für das jeweilige Suchverfahren betrachtet werden. Mehr Informationen zu den einzelnen Kriterien findest Du in der Erklärung zu den Sortieralgorithmen auf StudySmarter.

Suchalgorithmen Laufzeit

Die Laufzeit von Suchalgorithmen wird in den Best-Case, Average-Case und den Worst-Case unterschieden. Angegeben wird die Laufzeit mithilfe der sogenannten O-Notation.

Die O-Notation ist eine Methode in der Informatik, um den Aufwand von Algorithmen bzw. die Komplexität von Funktionen in Abhängigkeit ihrer Eingabegröße einzuordnen. Sie macht dadurch die Effizienz von Algorithmen vergleichbar.

Weitere Informationen zur O-Notation findest Du in der gleichnamigen Erklärung auf StudySmarter.

In der folgenden Übersicht sind die Laufzeiten von verschiedenen Suchalgorithmen auf einem Blick zusammengefasst. Steht nichts explizit dabei, ist der Average-Case angegeben.

SuchalgorithmusLaufzeit
Lineare SucheO(n)
Binäre SucheO(log n)
InterpolationssucheBest-Case: O(log(log(n)))Worst-Case: O(n)
BreitensucheBei Verwendung einer Adjazenzliste: O(|V| + |E|)Bei Verwendung einer Adjazenzmatrix: O(|V2|) oder O(n2)
TiefensucheO(|V| + |E|)
Dijkstra AlgorithmusBei Verwendung in Arrays: O(n2 + m)Bei Verwendung in einer PriorityQueue: O(n · log n + m · n)
Boyer-Moore AlgorithmusO(n/m)
Knuth-Morris-Pratt AlgorithmusO(n + m)

Suchalgorithmen – Das Wichtigste

  • Suchalgorithmen Informatik: Ein Suchalgorithmus ist ein Verfahren, bei dem Schritt-für-Schritt Daten innerhalb einer Datensammlung ausfindig gemacht werden.
  • Suchalgorithmen Anwendung: Suchalgorithmen können verwendet werden, um Daten, Listen oder Baumstrukturen zu durchsuchen.
  • Die Suchalgorithmen können in verschiedene Arten unterschieden werden:
    • Einfache Suchalgorithmen
    • Heuristische Suchalgorithmen
    • Weitere Suchalgorithmen
  • Beispiele für Suchalgorithmen sind: lineare Suche, binäre Suche, Interpolationssuche, Suche in Bäumen, Suchen in Graphen, Hash-Suche etc.
  • Suchalgorithmen Vergleich: Verglichen werden können Suchalgorithmen durch Kriterien wie die Laufzeit, den Speicherbedarf oder die Stabilität.

Nachweise

  1. betriebswirtschaft-lernen.net: Suchalgorithmus. (29.11.2022)
  2. javabeginners.de: Interpolationssuche. (29.11.2022)
  3. alexanderthamm.com: Suchalgorithmus. (29.11.2022)
  4. ionos.de: Die Hashtabelle – der schnelle Datenbankzugriff auf Hashwerte. (29.11.2022)

Häufig gestellte Fragen zum Thema Suchalgorithmen

Ein Suchalgorithmus ist ein Verfahren, bei dem Schritt-für-Schritt Daten innerhalb einer Datensammlung ausfindig gemacht werden.

Suchalgorithmen können in einfache und heuristische Verfahren unterschieden werden. Heuristische Algorithmen berücksichtigen dabei genauere Informationen über die zu durchsuchende Datenmenge, wie die Datenverteilung.  

Suchalgorithmen sind dafür da, um aus einer Datenmenge bestimmte Daten zu ermitteln. Wie genau ein Suchalgorithmus funktioniert, hängt dabei vom Verfahren ab.

Finales Suchalgorithmen Quiz

Suchalgorithmen Quiz - Teste dein Wissen

Frage

Ergänze

Ein ______ (1) ist ein Verfahren, bei dem ______ (2) Daten innerhalb einer Datensammlung ausfindig gemacht werden. 

Antwort anzeigen

Antwort

(1) Suchalgorithmus  

(2) Schritt-für-Schritt 

Frage anzeigen

Frage

Was ist sowohl bei Suchalgorithmen als auch bei Sortieralgorithmen ein wichtiger Vergleichsfaktor?

Antwort anzeigen

Antwort

Laufzeit (Zeitkomplexität)

Frage anzeigen

Frage

Nennen drei Arten verschiedener Suchalgorithmen.

Antwort anzeigen

Antwort

  • Einfache Suchalgorithmen 
  • Heuristische Suchalgorithmen
  • Weitere Suchverfahren

Frage anzeigen

Frage

Was kann mit Suchalgorithmen durchsucht werden?

Antwort anzeigen

Antwort

Daten, Listen, Baumstrukturen, Graphen usw. 

Frage anzeigen

Frage

Was ist ein Nachteil von einfachen Suchalgorithmen?

Antwort anzeigen

Antwort

Ein Nachteil ist, dass einfache Suchalgorithmen bei der Suche kein gutes Kosten-Nutzen-Verhältnis haben und meist eine relativ lange Laufzeit besitzen.

Frage anzeigen

Frage

Worin kann man bei heuristischen Suchalgorithmen unterscheiden?

Antwort anzeigen

Antwort

  • informierte Suchalgorithmen 
  • uninformierte Suchalgorithmen

Frage anzeigen

Frage

Ergänze

Die ______ Suche besucht zunächst "vielversprechende" Knoten in einem Baum. 

Antwort anzeigen

Antwort

informierte 

Frage anzeigen

Frage

Wahr oder falsch

Heuristische Algorithmen werden vor allem dann eingesetzt, wenn die Komplexität und Rechenleistung eines Algorithmus verringert werden soll.

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Ergänze

Bei der ______ Suche werden Knoten in einem Baum einfach der Reihe nach durchlaufen. 

Antwort anzeigen

Antwort

Uniformierten

Frage anzeigen

Frage

Nenne weitere Suchverfahren.

Antwort anzeigen

Antwort

  • Optimierende Suche
  • Suchverfahren für Zeichenketten

Frage anzeigen

Frage

Ergänze

Bei der ______ werden Werte bestimmten, vorher definierten, Variablen zugeordnet. 

Antwort anzeigen

Antwort

optimierenden Suche 

Frage anzeigen

Frage

Nenne mögliche Suchverfahren für Zeichenketten.

Antwort anzeigen

Antwort

  • Knuth-Morris-Pratt Algorithmus
  • Boyer-Moore Algorithmus
  • Karp-Rabin Algorithmus

Frage anzeigen

Frage

Wahr oder falsch

Die lineare Suche gehört zu den einfachen Suchalgorithmen.

Antwort anzeigen

Antwort

Wahr 

Frage anzeigen

Frage

Wahr oder falsch

Die binäre Suche ist eine Modifizierung der Interpolationssuche.

Antwort anzeigen

Antwort

Falsch

Frage anzeigen

Frage

Ergänze

Die Idee hinter dem Hashverfahren ist es, mithilfe eines ______ (1), einer ______ (2) und einer dazugehörigen ______ (3) eine sogenannte ______ (4) zu erzeugen. Die Hashadresse gibt dabei genau an, an welcher Stelle, bzw. in welchem Feld sich der Datensatz befindet.

Antwort anzeigen

Antwort

(1) Schlüssels 

(2) Hashfunktion  

(3) Hashadresse  

(4) Hashtabelle  

Frage anzeigen

Frage

Welche Kriterien können zum Vergleich von Suchalgorithmen verwendet werden?

Antwort anzeigen

Antwort

  • Laufzeit / Komplexität
  • Zusätzlicher Speicherbedarf / Platzkomplexität
  • Stabilität
  • Intern vs. extern / in-place vs. out-of-place
  • Rekursiv vs. iterativ

Frage anzeigen

Teste dein Wissen mit Multiple-Choice-Karteikarten

ErgänzeDie ______ Suche besucht zunächst "vielversprechende" Knoten in einem Baum. 

Wahr oder falschHeuristische Algorithmen werden vor allem dann eingesetzt, wenn die Komplexität und Rechenleistung eines Algorithmus verringert werden soll.

ErgänzeBei der ______ Suche werden Knoten in einem Baum einfach der Reihe nach durchlaufen. 

Weiter

Karteikarten in Suchalgorithmen16

Lerne jetzt

Ergänze

Ein ______ (1) ist ein Verfahren, bei dem ______ (2) Daten innerhalb einer Datensammlung ausfindig gemacht werden. 

(1) Suchalgorithmus  

(2) Schritt-für-Schritt 

Was ist sowohl bei Suchalgorithmen als auch bei Sortieralgorithmen ein wichtiger Vergleichsfaktor?

Laufzeit (Zeitkomplexität)

Nennen drei Arten verschiedener Suchalgorithmen.

  • Einfache Suchalgorithmen 
  • Heuristische Suchalgorithmen
  • Weitere Suchverfahren

Was kann mit Suchalgorithmen durchsucht werden?

Daten, Listen, Baumstrukturen, Graphen usw. 

Was ist ein Nachteil von einfachen Suchalgorithmen?

Ein Nachteil ist, dass einfache Suchalgorithmen bei der Suche kein gutes Kosten-Nutzen-Verhältnis haben und meist eine relativ lange Laufzeit besitzen.

Worin kann man bei heuristischen Suchalgorithmen unterscheiden?

  • informierte Suchalgorithmen 
  • uninformierte Suchalgorithmen

Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.

  • Karteikarten & Quizze
  • KI-Lernassistent
  • Lernplaner
  • Probeklausuren
  • Intelligente Notizen
Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App! Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Melde dich an für Notizen & Bearbeitung. 100% for free.

Fang an mit StudySmarter zu lernen, die einzige Lernapp, die du brauchst.

Jetzt kostenlos anmelden
Illustration