Lineare Suche in Python: Ein Leitfaden für Anfänger mit Beispielen

Wenn es um Suchalgorithmen geht, ist die lineare Suche einer der einfachsten. Wenn du schon einmal eine Liste von Artikeln einzeln durchgesehen hast, bis du gefunden hast, wonach du gesucht hast, dann hast du bereits eine lineare Suche durchgeführt!

Die lineare Suche ist nicht nur einfach zu verstehen, sondern auch nützlich, weil sie im Gegensatz zu einigen anderen Suchalgorithmen mit unsortierten Daten arbeitet. Diese Vielseitigkeit macht sie zu einer nützlichen Option in Szenarien, in denen eine Datensortierung nicht möglich ist. Ich werde in diesem Lernprogramm Python verwenden. Wenn du also vor dem Start dein Wissen über Python auffrischen möchtest, schau dir den Python Programming Skill Track an.

Was ist die lineare Suche?

Die lineare Suche ist ein Algorithmus, der einen bestimmten Wert innerhalb einer Liste findet, indem er jedes Element einzeln überprüft. Er beginnt beim ersten Eintrag, vergleicht ihn mit dem Ziel und bewegt sich dann weiter durch die Liste, bis er entweder das Ziel findet oder das Ende der Liste erreicht. Es ist ein einfacher und intuitiver Algorithmus.

Die lineare Suche benötigt keine sortierten Daten, um zu funktionieren, und wird daher hauptsächlich bei unsortierten Datensätzen verwendet. Das ist besonders praktisch, wenn eine Sortierung nicht möglich ist oder du mit Daten in ihrer Rohform arbeitest. Dieser Vorteil hat jedoch seinen Preis: Er ist nicht so effizient wie andere Algorithmen, die vorsortierte Daten benötigen.

Die lineare Suche ist ideal, wenn du mit relativ kleinen Datensätzen arbeitest oder wenn das Sortieren der Daten nicht machbar ist. Das folgende Diagramm gibt eine vereinfachte Erklärung.

Wahl der linearen Suche

Werfen wir einen Blick auf die Vorteile und auch einen deutlichen Nachteil: 

Warum die lineare Suche?

Meiner Meinung nach hat die lineare Suche drei entscheidende Vorteile:

Wenn Einfachheit der Schlüssel ist

Einer der größten Vorteile der linearen Suche ist ihre Einfachheit. Der Algorithmus ist leicht zu verstehen und umzusetzen. Du musst dich nicht um eine komplexe Sortierung oder Aufteilung der Daten kümmern. Beginne einfach am Anfang der Liste und überprüfe jedes Element, bis du gefunden hast, wonach du suchst.

Wenn du keine Zeit zum Sortieren hast

Im Gegensatz zu anderen Suchalgorithmen wie der binären Suche muss der Datensatz bei der linearen Suche nicht sortiert werden. Das macht sie perfekt, wenn du etwas schnell finden musst.

Wenn du Vielseitigkeit brauchst

Ein weiterer Vorteil der linearen Suche ist, dass sie vielseitig ist. Sie funktioniert nicht nur mit Arrays, sondern auch mit anderen Python-Datenstrukturen, wie z.B. verknüpften Listen. Solange du nacheinander auf die Elemente zugreifen kannst, kann die lineare Suche die Arbeit erledigen. Es ist flexibel genug, um verschiedene Datentypen zu verarbeiten, von Zahlen über Strings bis hin zu Objekten.

Warum sollte man die lineare Suche überdenken?

Es gibt ein Problem zu bedenken:

Wenn Effizienz eine Rolle spielt

Der größte Nachteil der linearen Suche ist ihre Ineffizienz, besonders bei großen Datensätzen. Die Zeitkomplexität ist O(n), was bedeutet, dass du im schlimmsten Fall jedes einzelne Element der Liste überprüfen musst! Das kann die Arbeit sehr verlangsamen, wenn du mit Tausenden oder Millionen von Einträgen arbeitest. Bei kleinen Datensätzen kann diese Ineffizienz jedoch vernachlässigbar sein.

Einen linearen Suchalgorithmus in Python implementieren

In Python gibt es zwei gängige Möglichkeiten, eine lineare Suche zu schreiben: die iterative Methode und die rekursive Methode. Um diese beiden Methoden zu demonstrieren, erstellen wir zunächst einen einfachen Datensatz mit 100 Zahlen ohne Duplikate.

numbers = [12, 7, 19, 3, 15, 25, 8, 10, 42, 56, 77, 23, 89, 65, 33, 99, 14, 2, 37, 81,
           48, 64, 22, 91, 6, 40, 59, 87, 28, 53, 74, 9, 16, 39, 71, 93, 54, 32, 61, 27,
           35, 18, 49, 68, 83, 46, 57, 29, 95, 11, 26, 44, 78, 5, 66, 73, 41, 85, 31, 50,
           20, 63, 88, 34, 90, 60, 67, 4, 52, 36, 62, 80, 21, 84, 98, 13, 45, 69, 30, 38,
           47, 17, 92, 55, 70, 76, 82, 24, 43, 1, 100, 58, 96, 75, 97, 94, 86, 72, 51, 79]

Iterative Methode

Der iterative Ansatz ist wahrscheinlich der einfachste Weg, um die lineare Suche zu verstehen. Du gehst in einer Schleife durch die Liste und überprüfst jedes Element, bis du das Ziel findest oder das Ende erreichst.

Zuerst erstellen wir unsere Funktion:

1. Wir gehen in einer Schleife durch jedes Element der Liste arr.

2. Wir werden jedes Element mit dem Ziel vergleichen.

3. Wenn wir eine Übereinstimmung finden, geben wir den Index zurück, in dem das Ziel gefunden wurde.

4. Wenn wir die Schleife beenden, ohne das Ziel zu finden, geben wir 1 zurück, um anzuzeigen, dass das Element nicht vorhanden ist.

def linear_search_iterative(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return the index if the target is found
    return -1  # Return -1 if the target is not found

Als Nächstes führen wir unsere Funktion auf unserem Datensatz aus und drucken das Ergebnis:

# Run the function on the numbers list
target = 91
index = linear_search_iterative(numbers, target)

if index != -1:
    print(f"Target {target} found at index {index}")
else:
    print(f"Target {target} not found!")

Wenn wir diesen Code ausführen, finden wir den Zielwert am 23.

Rekursive Methode

Die rekursive Methode verwendet eine Funktion, die sich selbst aufruft, um die Liste zu durchsuchen. Jeder rekursive Aufruf verarbeitet ein Element nach dem anderen und geht dann zum nächsten Element über. Das geht so lange, bis das Ziel gefunden oder das Ende der Liste erreicht ist.

Lass uns unsere rekursive Funktion erstellen:

1. Wir beginnen mit der Überprüfung des ersten Elements (bei Index 0).
2. Wenn das Ziel übereinstimmt, geben wir den Index zurück.
3. Wenn das Ziel nicht übereinstimmt, rufen wir die gleiche Funktion rekursiv auf, erhöhen aber den Index um 1, um das nächste Element zu prüfen.
4. Die Rekursion geht weiter, bis wir das Ziel finden oder das Ende der Liste erreichen.

def linear_search_recursive(arr, target, index=0):
    if index >= len(arr):  # Base case: we've checked all elements
        return -1
    if arr[index] == target:  # Base case: target found
        return index
    return linear_search_recursive(arr, target, index + 1)  # Recursive case: check next element

Wir können denselben Code wie oben verwenden, um diese Funktion auszuführen, und sie gibt denselben Indexwert für unser Ziel zurück: 23.

Bedenke, dass dieser Ansatz mehr Speicherplatz verbraucht, weil jeder rekursive Aufruf eine neue Ebene zum Aufrufstapel hinzufügt. Unter Rekursive Funktionen in Python verstehen erfährst du mehr über die Rekursion.

Zeit und Raum Komplexität

Eine Möglichkeit, die Effizienz eines Algorithmus zu bewerten, ist die Betrachtung seiner Zeit- und Raumkomplexität. Im Tutorial Analyzing Complexity of Code through Python erfährst du mehr über die verschiedenen Möglichkeiten, die Komplexität eines Algorithmus zu messen.

Zeitliche Komplexität

Die Zeitkomplexität eines Algorithmus bezieht sich darauf, wie die Zeit, die er zur Fertigstellung benötigt, mit der Größe der Eingabe zunimmt. Die Zeitkomplexität der linearen Suche ist O(n), wobei n die Anzahl der Elemente in der Liste ist. Das bedeutet, dass der Algorithmus im schlimmsten Fall jedes einzelne Element überprüfen muss, bevor er das Ziel findet (oder feststellt, dass das Ziel nicht in der Liste enthalten ist). Das ist ziemlich ineffizient, besonders bei großen Datensätzen. Deshalb funktioniert die lineare Suche am besten, wenn wir kleinere, unsortierte Datensätze haben, die wir nur einmal durchsuchen müssen.

Raumkomplexität

Die Raumkomplexität eines Algorithmus ist ein Maß dafür, wie viel Speicherplatz er benötigt, wenn die Größe der Eingabe wächst. Die Raumkomplexität des linearen Suchalgorithmus hängt davon ab, welche Methode wir verwenden. Bei der iterativen Methode ist die Raumkomplexität O(1), d.h. der Algorithmus benötigt unabhängig von der Größe der Eingabeliste eine konstante Menge an Speicherplatz. Das liegt daran, dass die iterative Version keinen zusätzlichen Speicher benötigt, abgesehen von der Eingabeliste und ein paar Variablen, um den aktuellen Index zu behalten.

Bei der rekursiven Methode ist die Raumkomplexität O(n), d.h. der benötigte Speicher wächst linear mit der Größe der Eingabeliste. Das liegt an den rekursiven Funktionsaufrufen, die dem Aufrufstapel für jedes Element in der Liste Ebenen hinzufügen. Eine größere Liste benötigt mehr Speicherplatz, um diese Aufrufe zu speichern, wodurch der rekursive Ansatz weniger platzsparend ist.

Anwendungen der linearen Suche in der realen Welt

Die lineare Suche ist zwar nicht der effizienteste Algorithmus für große Datensätze, aber sie ist in vielen Situationen praktisch einsetzbar. Werfen wir einen Blick auf einige Situationen, in denen die lineare Suche das beste Werkzeug für den Job ist.

Kleine Datensätze, bei denen eine Sortierung nicht sinnvoll ist

Die lineare Suche ist oft meine erste Wahl, wenn ich mit kleinen Datensätzen zu tun habe, die es nicht wert sind, sortiert zu werden. In diesen Fällen kann die Einfachheit der linearen Suche effizienter sein als der Aufwand für die Sortierung der Daten bei komplexeren Suchalgorithmen.

Das erste Vorkommen eines Ziels finden

Ein weiterer häufiger Anwendungsfall für die lineare Suche ist, wenn du das erste Vorkommen eines Zielwerts finden musst. Da sich die lineare Suche Element für Element durch die Liste bewegt, findet sie natürlich die erste Instanz des Ziels und gibt dessen Position zurück. Das kann besonders nützlich sein, wenn du z.B. in einer Zeichenkette nach dem ersten Auftreten eines Zeichens suchst.

Wenn eine minimale Einrichtung erforderlich ist

Manchmal macht die Einfachheit der linearen Suche sie zur besten Option. Wenn du zum Beispiel schnell Daten durchsuchst, die du nicht wiederverwenden willst, oder wenn du schnell eine Antwort brauchst, kann die lineare Suche mit ihren minimalen Einstellungen Zeit sparen.

Lineare Suche vs. Andere Suchalgorithmen

Die lineare Suche ist nur einer von vielen Suchalgorithmen, die es gibt. Schauen wir uns zwei weitere gängige Suchalgorithmen an: die binäre Suche und das Hash-Lookup.

Lineare Suche vs. Binäre Suche

Die binäre Suche ist ein Algorithmus, der die Position eines Zielwertes innerhalb eines sortierten Feldes findet, indem er das Suchintervall wiederholt halbiert. Sie hat eine Zeitkomplexität von O(log n) und ist damit viel effizienter als die lineare Suche. Es funktioniert jedoch nur bei sortierten Daten. Wenn dein Datensatz sortiert ist, ist die binäre Suche fast immer die bessere Wahl, weil sie den Suchraum mit jedem Schritt halbiert und so die Anzahl der Vergleiche, die nötig sind, um das Ziel zu finden, drastisch reduziert.

Die lineare Suche kann in Situationen, in denen deine Daten unsortiert sind, besser geeignet sein, da die lineare Suche mit jedem Datensatz funktioniert, egal ob sortiert oder nicht. Mit einer Zeitkomplexität von O(n) ist die lineare Suche bei sortierten Datensätzen jedoch weit weniger effizient.

Lineare Suche vs. Hash Lookup

Hash Lookup ist eine Methode, die eine Hashtabelle verwendet, um ein Element schnell zu finden. Mit einer Zeitkomplexität von O(1) ist sie deutlich schneller als die lineare oder binäre Suche. Diese Geschwindigkeit hat jedoch ihren Preis: Du musst zuerst eine Hashtabelle erstellen, was sowohl Zeit als auch zusätzlichen Speicher benötigt. Hash-Lookups funktionieren am besten, wenn du große Datensätze mehrmals durchsuchen musst, damit sich die anfängliche Einrichtung mit der Zeit auszahlt.

Im Gegensatz dazu erfordert die lineare Suche keine Vorbereitungen, was sie zu einer einfacheren Option macht. Sie ist die bessere Wahl, wenn du nur einmal oder nur wenige Male suchen musst und der zusätzliche Zeitaufwand für das Einrichten einer Hashtabelle nicht gerechtfertigt ist. Die lineare Suche kann auch platzsparender sein, weil du keine Hashtabelle speichern musst, um den Algorithmus zu verwenden.

Häufige Fallstricke und wie du sie vermeidest

Obwohl die lineare Suche ein einfacher Algorithmus ist, gibt es ein paar häufige Fehler, auf die du achten solltest.

Off-by-One-Fehler in der Iteration

Einer der häufigsten Fehler bei der Umsetzung einer linearen Suche ist ein Off-by-One-Fehler. Dies wird dadurch verursacht, dass die Iteration am falschen Index gestartet oder gestoppt wird. Es ist wichtig, daran zu denken, dass Python-Listen einen Null-Index haben, d.h. das erste Element hat einen Index von 0. Wenn du das vergisst, kann es passieren, dass du versehentlich das erste Element überspringst oder einen Schritt zu weit iterierst, was zu falschen Ergebnissen oder Fehlern führt.

Missverständnis des zurückgegebenen Index

Ein weiterer häufiger Fallstrick ist das Missverständnis, was die Funktion zurückgibt, wenn das Ziel nicht in der Liste gefunden wird. Viele Suchalgorithmen (einschließlich der linearen Suche) geben per Konvention -1 zurück, um anzuzeigen, dass das Ziel nicht vorhanden ist. Manche Anfänger nehmen jedoch an, dass None, False oder ein anderer Wert zurückgegeben wird, was zu Verwirrung bei der Interpretation der Ergebnisse führt.

Wann man die lineare Suche nicht verwenden sollte

Wie wir bereits erwähnt haben, wird die lineare Suche bei größeren Datenmengen schnell ineffizient. Aus diesem Grund ist sie am besten für kleine, unsortierte Datensätze oder schnelle, einmalige Suchen geeignet.

Fazit

Als eine der einfachsten Suchmethoden prüft die lineare Suche jedes Element in einer Liste der Reihe nach und ist daher leicht zu verstehen und zu implementieren. Die lineare Suche ist eine zuverlässige Wahl für die schnelle, einmalige Suche in kleinen Datensätzen, insbesondere wenn die Daten unsortiert sind.

Wenn du dich für Suchalgorithmen interessierst, schau dir meine anderen Artikel in dieser Reihe an: Binäre Suche in Python, Depth-First Search in Python und Breadth-First Search in Python. Das könnte dich auch interessieren: AVL Tree: Complete Guide With Python Implementation und Introduction to Network Analysis in Python als weiterführende Themen.