6 Arten von Suchalgorithmen und wie sie funktionieren

Sie können sich Suchalgorithmen als digitale Detektive vorstellen, die das Gesuchte in riesigen Datensammlungen wie Websites oder Datenbanken mit möglichst wenigen Schritten finden.

Von Google und Amazon bis Facebook und Netflix spielen Suchalgorithmen eine wichtige Rolle in digitalen Interaktionen im Alltag.

In diesem Artikel erfahren Sie mehr über die häufigsten Arten von Suchalgorithmen, ihre Zeitkomplexität, wie ihre Suchprozesse funktionieren und praktische Anwendungen in der Informatik.

Eine geringere durchschnittliche Fallkomplexität ist besser für eine schnellere Leistung, besonders bei großen Inputs. Algorithmen wie die binäre Suche O(log n) sind höchst effizient.

Andererseits können höhere Komplexitäten wie O(n) für größere Datensätze aufgrund des Wachstums der linearen Suche oder einer schlechteren Laufzeit unpraktisch werden. Jedoch hängt die Effizienz auch von Faktoren wie Datenstrukturen, dem Kontext eines Problems, Ressourcen und Anwendungsanforderungen ab.

1. Lineare Suchalgorithmen

Die lineare Suche, auch bekannt als sequentielle Suche, iteriert sequentiell durch Reihenelemente in einem Datensatz und vergleicht sie mit dem Zielelement, bis sie einen genauen Treffer findet. Wenn die Suchfunktion das Ende der Reihe ohne einen Treffer erreicht, heißt das, dass das Zielelement in dem Datensatz nicht vorhanden ist.

Das Zielelement, nach dem sie suchen, könnten Zahlen, Strings, Objekte oder andere Datentypen sein, die in einer Reihe aufbewahrt werden. Diese Flexibilität macht die lineare Suche a zu einem abwechslungsreichen Algorithmus, der auf viele verschiedene Datentypen angewendet werden kann.

Sehen wir uns ein echtes Beispiel an, um diesen Suchprozess besser zu verstehen.

Nehmen wir an, dass Sie eine unsortierte Liste mit Ganzzahlen haben, die das Alter von Menschen in einer Gruppe darstellt. Ihr Ziel ist es, herauszufinden, ob ein bestimmtes Alter – sagen wir 25 – in der Reihe vorhanden ist. Sie würden am Beginn der Reihe anfangen und jedes Element überprüfen, bis sie entweder das Alter 25 finden oder das Ende der Reihe erreichen.

Die Ausführungszeit eines linearen Suchalgorithmus ist proportional zu der Reihengröße. Die rechnerische Komplexität der linearen Suche ist O(n), wobei n die Zahl der Elemente in der Reihe ist.

Anwendungen der linearen Suche

• Simple Suchaufgaben: Die lineare Suche wird oft für ein großes Spektrum von grundlegenden Suchaufgaben verwendet, bei denen der Datensatz klein ist oder wo die zusätzliche Komplexität anderer Algorithmen nicht gewährleistet ist. Zum Beispiel bei der Suche in einer kurzen Liste mit Namen oder Zahlen.
• Lineare Datenstrukturen: Die lineare Suche ist fundamental für viele lineare Datenstrukturen wie Reihen, Listen und Stapeln. Sie wird meist verwendet, um diese Strukturen zu durchsuchen und spezifische Elemente zu finden oder Vorgänge durchzuführen.
• Ungeordnete Reihen: Da die lineare Suche jedes Element sequentiell überprüft, findet es Items, egal wo sie sich in der Reihe befinden.

2. Binäre Suchalgorithmen

Die binäre Suche ist ein effizienter Algorithmus, mit dem in einer sortierten Liste ein Zielwert gefunden werden kann. Sie teilt die Suchintervalle mit der binären Suchmethode mehrmals in der Hälfte. Dann vergleicht sie den Zielwert mit dem mittleren Element und fährt mit dem linken oder rechten Teil einer Reihe fort. Dieser Vorgang wird fortgesetzt, bis der Zielwert gefunden wurde. Das Suchintervall könnte auch keine Ergebnisse bringen, wenn das Ziel in der Reihe nicht vorhanden ist.

Sehen wir uns ein Beispiel der binären Suche an, um einen spezifischen numerischen Wert zu finden.

Stellen Sie sich diese Zahlenreihe vor: [2,5,8,12,16,23,38,56,72,91]. Sie möchten die Zahl 23 finden.

Sie beginnen, indem sie sich das mittlere Element (Wurzelknoten) ansehen, was 16 ist. Da 23 größer ist als 16, sehen Sie sich nur die Zahlen rechts von 16 an. Als Nächstes sehen Sie sich das mittlere Element dieses Teils an, was 56 ist. Da 23 kleiner ist als 56, sehen Sie sich nur die Zahlen links von 56 an. Nun sehen Sie sich erneut das mittlere Element an, was 23 ist. Sie haben den Suchschlüssel gefunden!

Die Ausführungszeit des binären Suchalgorithmus ist O (log n), wobei n die Anzahl der Elemente in der Reihe ist.

Anwendungen der binären Suche

• Suche in Datenbanken: Dies ist ein effektiver Algorithmus für die Datenbanksuche, mit der man Einträge rasch basierend auf indexierten Feldern wie IDs oder Schlüsseln finden kann.
• Elemente in geordneten Reihen finden: Die binäre Suche findet effizient Elemente in sortierten Reihen, was bei indexbasierten Datenstrukturen und der Suche nach Worten in einem Wörterbuch oder nach Items in einer sortierten Liste nützlich ist.
• Algorithmische Grundlage: Sie dient als Grundstein für die Entwicklung ausgefeilter maschineller Lernalgorithmen. Die binäre Suche hilft bei der Schulung neuraler Netzwerke und Optimierung von Model-Hypoparametern.
• Algorithmen optimieren: Die binäre Suche wird in Algorithmen inklusive Aufteilungsstrategien eingesetzt, um Probleme wie das Finden von Quadratwurzeln oder Spitzenelementen in Reihen effizient zu lösen.
• Suche in Bäumen: Binäre Suchbäume (BSTs) nutzen diesen Algorithmus, um Elemente effizient zu suchen, einzufügen und zu löschen, während gleichzeitig die Ordnung des Baums aufrechterhalten wird.

3. Interpolationssuche

Wenn Werte in einer geordneten Reihe gleichmäßig verteilt sind, bietet die Interpolationsuche einen Vorteil an, den die binäre Suche nicht hat. Bei der Interpolation werden neue Datenpunkte in der Reihe des bekannten Suchraums erstellt.

Während die binäre Suche sich immer auf das mittlere Element konzentriert, passt die Interpolationssuche die Suchposition basierend auf dem gesuchten Zielwert an. Wenn ein Suchschlüssel beispielsweise näher am Ende ist, beginnt die Interpolationssuche die Suche nach Daten am Ende.

Stellen Sie sich vor, dass Sie in einer Preisliste für Ihren Shop nach einem bestimmten Preis suchen. Die Preise sind vom niedrigsten bis zum höchsten geordnet. Anstatt die Hälfte der Liste zur überprüfen (wie bei der binären Suche), schätzt die Interpolationssuche ab, wo sich der Preis am wahrscheinlichsten befindet, indem sie den Wert mit dem höchsten und dem niedrigsten Preis vergleicht. Dann wiederholt sie diesen Vorgang, bis der Preis gefunden wird.

Die Ausführungszeit des Interpolationsalgorithmus ist O(log log n), wobei n die Zahl der Elemente in der Reihe ist.

Anwendungen der Interpolationssuche

• Suche in Datenbanken: Die Interpolationssuche wird oft in Datenbanken verwendet, um Aufzeichnungen basierend auf einigen Schlüsselelementen zu durchsuchen.
• Suche in langen Reihen: Dieser Suchalgorithmus ermöglicht eine effizientere Suche in längeren sortierten Reihen, besonders wenn die Verteilung der Werte gleichmäßig ist. Sie kann auf verschiedene Felder angewendet werden, wie die Computerwissenschaft, wo große Datensätze effizient durchsucht werden müssen.
• Daten von Symboltabellen abrufen: Die Interpolationssuche kann bei Symboltabellen verwendet werden, bei denen die Schlüssel mit Werten in Verbindung stehen. In Programmiersprachen werden Symboltabellen beispielsweise verwendet, um Variablen, Funktionen und andere Bezeichner zu speichern. Die Interpolationssuche kann Informationen, die mit einem bestimmten Bezeichner in Verbindung stehen, rasch finden.
• Zeitkritische Anwendungen: Da die Interpolationssuche Daten rasch abrufen kann, eignen sie sich gut für zeitkritische Anwendungen.
• Hashtabelle: Effizient für das Finden von Daten, wenn sie mit der Hashfunktion kombiniert werden.

4. Sprungsuche

Die Sprungsuche, auch bekannt als Blocksuche – wurde speziell für sortierte Reihen entwickelt. Im Gegensatz zur linearen Suche, die sich Elemente nacheinander ansieht, bewegt sich die Sprungsuche in festgelegten Inkrementen, wobei mehrere Elemente übersprungen werden, was die Suche beschleunigt.

Wenn das Zielelement sich in einem bestimmten Bereich befindet, führt der Algorithmus in dem Block eine lineare Suche durch. Dieser Ansatz verringert die erforderlichen Vorgänge und verbessert die Sucheffizienz.

Sehen wir uns ein Beispiel eines Sprungsuchalgorithmus an.

Stellen Sie sich vor, Sie suchen in einer langen Zahlenliste eine bestimmte Zahl und möchten nicht jede Zahl überprüfen.

1. Entscheiden Sie, wie viele Zahlen Sie jedes Mal überspringen möchten: Sagen wir, wir überspringen jedes Mal 3 Zahlen.
2. Beginnen Sie, die Liste zu durchsuchen und jedes Mal die gewählte Anzahl zu überspringen, bis Sie eine Zahl finden, die gleich oder größer als die Zahl ist, nach der Sie suchen.
3. Sobald Sie einen Bereich gefunden haben, in dem sich die Zahl vielleicht befindet, müssen Sie eine lineare Suche durchführen, bis die Zielzahl gefunden wurde.

Die Ausführungszeit des Sprungsuchalgorithmus ist O(√n), wobei n die Anzahl der Elemente in einer sortierten Reihe ist.

Anwendungen der Sprungsuche

• JavaScript-Anwendungen: Die Sprungsuche optimiert den Suchvorgang in JavaScript-Anwendungen, verbessert die Effizienz und die Reaktivität.
• Suche in Datenbanksystemen: Dieser Algorithmus sucht nach Aufzeichnungen basierend auf einigen Schlüsselelementen in größeren Datenbanken.
• Datenabruf von visuellen Medien: Die Sprungsuche findet rasch ein bestimmtes Bild in einer großen Videodatei, indem sie eine fixe Anzahl von Bildern auf einmal überspringt.

5. Exponentielle Suche

Der exponentielle Suchalgorithmus – auch bekannt als doppelte oder galoppierende Suche – unterscheidet sich von der Sprungsuche, da er die Reihe anders teilt und in den Abteilungen eine andere Suchmethode einsetzt. Während die Sprungsuche die Reihe in Blöcke aufteilt und die lineare Suche verwendet, teilt die exponentielle Suche die Reihe mit exponentiellen Potenzen von 2 auf und wendet die binäre Suche an.

Im Grunde durchläuft die Suchfunktion die gesamte Reihe von links und segmentiert sie in kleinere Abteile mit einer Potenz von 2. Der Algorithmus führt in diesen Blöcken eine binäre Suche durch, bis das Ziel gefunden wird.

Da der Suchalgorithmus etwas komplex sein kann, möchten wir ihn mit einem Beispiel aus der echten Welt darstellen.

Stellen Sie sich vor, Sie haben ein Bücherregal mit Büchern, die alphabetisch nach Titel sortiert sind. Sie suchen nach einem bestimmten Buch, zum Beispiel „Harry Potter und der Stein des Weisen”. Anstatt sich jedes Buch einzeln anzusehen, verwenden Sie die exponentielle Suche.

So funktioniert sie:

1. Anfangspunkt: Sie beginnen mit dem ersten Buch auf der linken Seite des Bücherregals. Wenn es nicht das richtige Buch ist, fahren Sie fort.
2. Bewegung nach rechts und Verdoppelung des Suchfensters: Wenn sich „Harry Potter und der Stein des Weisen” in einer dieser Positionen befindet, sind Sie fertig.
3. Vorgang wiederholen: Wiederholen Sie diesen Schritt und verdoppeln Sie die Spanne jedes Mal, bis Sie das Buch finden.

Während das nicht genau die richtige Anwendung der exponentiellen Suche ist, hilft das Beispiel zu zeigen, wie schnell man ein Buch finden kann, ohne sich jedes einzeln anzusehen.

Die Ausführungszeit eines exponentiellen Suchalgorithmus ist O(log n), wobei n die Anzahl der Elemente in der sortierten Reihe ist.

Anwendungen der exponentiellen Suche

• Daten in großen sortierten Reihen finden: Die exponentielle Suche findet Elemente in großen sortierten Reihen wie Produktauflistungen schnell, indem sie die Suchspanne exponentiell erweitert. Das ist ideal für Situationen, in denen die lineare Suche zu langsam ist.
• Dateisysteme durchsuchen: Dieser Algorithmus verbessert Suchanfragen in Dateisystemen, da er Dateien oder Verzeichnisse innerhalb von Verzeichnisstrukturen mithilfe einer exponentiellen Erweiterung der Suchspanne schnell findet.

6. Ternäre Suche

Die ternäre Suche ist ein Suchalgorithmus, der verwendet wird, um die Position eines bestimmten Wertes in einer sortierten Reihe zu finden. Im Gegensatz zur binären Suche, die Reihen in zwei Teile aufteilt, teilt die ternäre Suche sie in drei auf. Indem der Zielwert mit Elementen an zwei Stellen verglichen wird und die Reihe in drei Teile gespalten wird, kann die Suchfunktion die Suchfläche effizient eingrenzen.

Nutzen wir die ternäre Suche zum Beispiel, um die Zahl 6 in einer Reihe [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] zu finden.

• Suchbereich teilen:
  • Teilen Sie Ihren Suchbereich in drei Teile, indem Sie zwei Spaltungspunkte finden: Ein Punkt befindet sich etwa im ersten Drittel von links (sagen wir 4) und der zweite Punkt befindet sich etwa im zweiten Drittel von links (sagen wir 8).
  • Dadurch wird der Bereich in [1, 4], (5, 8) und [9, 10] geteilt.
• Mit dem Ziel vergleichen:
  • Überprüfen Sie, ob die Zahl, nach der wir suchen (6) gleich 4 oder 8 ist.
  • Sie ist nicht gleich 4 oder 8, also müssen Sie Ihre Punkte, basierend darauf, wo sich 6 eventuell befindet, anpassen:
    • Da 6 größer als 4, aber kleiner als 8 ist, bewegen wir den linken Punkt zu 5 und den rechten zu 7.
• Wiederholen oder abschließen:
  • Wiederholen Sie diesen Vorgang mit dem verkleinerten Suchraum, bis sie die Zahl 6 finden oder keinen Suchraum mehr haben.
  • So verringern Sie den Suchraum auf [6, 6] und finden die Zahl, nach der Sie suchen!

Die Ausführungszeit eines ternären Suchalgorithmus ist O(log3 n), wobei n die Anzahl der Elemente in einer sortierten Reihe ist.

Anwendungen der ternären Suche

• Unimodale Funktionen: Die ternäre Suche wird auf unimodale Funktionen angewendet, um die maximalen oder minimalen Werte zu identifizieren. Unimodale Funktionen haben den höchsten Wert.

Fazit

Die Anwendungen verschiedener Arten von Suchalgorithmen sind vielfältig und umfangreich und reichen vom Durchsuchen großer Datenbanken über die Optimierung von Anwendungen bis hin zur Grundlage für die Entwicklung fortgeschrittener Algorithmen des maschinellen Lernens zum Suchen.

Wenn Sie die Zeit- und Raumkomplexität, Fähigkeiten sowie Vor- und Nachteile jedes der erwähnten Algorithmen berücksichtigen, können Sie fundierte Entscheidungen treffen. Ob es sich um eine Aufgabe in Ihrer Informatik-Klasse oder um die Entwicklung der nächsten bahnbrechenden App handelt – durch die Beherrschung von Techniken wie binärer Suche, DFS, BFS und Divide-and-Conquer können Sie das volle Potenzial von Datenstrukturen nutzen und Ihre Systemleistung verbessern.

Wenn Sie speziell die Suche für einen Online-Shop entwickeln oder bewerten, funktionieren die Mechaniken in der Praxis etwas anders. Siehe wie E-Commerce-Suche funktioniert hinter den Kulissen.

Häufig gestellte Fragen