Einführung in den linearen Suchalgorithmus: Einführung & Funktionen [mit Beispielen]

Was ist Suchen?

Suchen ist der Prozess, ein bestimmtes Element in einer Liste von Elementen zu finden. Es hilft bei der Suche nach einem bestimmten Datensatz. Daher ist es eine Technik, den Ort eines bestimmten Gegenstands zu identifizieren. Der Erfolg eines Suchvorgangs hängt davon ab, ob das zu durchsuchende Objekt identifiziert wurde oder nicht.

Die Datenstruktur ermöglicht das Suchen von Daten durch zwei Methoden.

1. Lineare Suche oder sequentielle Suche
2. Binäre Suche

Lineare Suche

Lineare Suchalgorithmen sind eine Art Algorithmus zum sequentiellen Durchsuchen der Daten. Dieser Algorithmus findet ein gegebenes Element mit der Komplexität O(n). Es wird auf eine Sammlung von Elementen angewendet. Jedes einzelne Datenelement wird sequentiell durchsucht und zurückgegeben, wenn es mit dem gesuchten Element übereinstimmt. Wenn keine Übereinstimmungen gefunden werden, wird die Suche bis zum Ende der gesammelten Daten fortgesetzt. Es ist im Grunde eine Technik, jedes Element zu erkunden, während man die Liste durchläuft. Der Suchalgorithmus kann sowohl auf die sortierten als auch auf die unsortierten Daten angewendet werden. Die praktisch lineare Suche wird selten verwendet, da andere Suchalgorithmen wie binäre Suchalgorithmen und Hashtabellen schnellere Suchoptionen bieten.

Schritte im linearen Suchalgorithmus

• Auslesen des Suchelements durch den Benutzer.
• Das zu suchende Element wird mit dem ersten Element der Liste komprimiert.
• Wenn die Elemente übereinstimmen, wird eine Rückgabe generiert.
• Wenn die Elemente nicht übereinstimmen, wird das zu suchende Element mit dem zweiten Element der Liste verglichen.
• Der Vorgang wird wiederholt, bis das Element übereinstimmt.

Merkmale linearer Suchalgorithmen

1. Es wird normalerweise auf eine kleine Liste unsortierter oder ungeordneter Daten angewendet.
2. Die Zeit hängt linear von der Anzahl der Elemente ab und hat daher eine Zeitkomplexität, wenn O (n).
3. Die Implementierung ist sehr einfach.

Lineare Suchalgorithmen

Eine kontinuierliche Schleifenmethode wird fortgesetzt, bis das Element gefunden wird

• Algorithmus Seqnl_Search(list, item)
• Pre: Liste != ;
• Post: Gibt den Index des Artikels zurück, falls gefunden, ansonsten: 1
• Index <-fi
• while index < list.Cnt und list[index] != item //cnt: Zählervariable
• index <- index + 1
• Ende während
• if index < list.Cnt und list[index] = item
• Rückgabeindex
• Ende wenn
• Rückkehr: 1
• Ende Seqnl_Search

Beispiel für lineare Suche

Problem: Schreiben Sie bei einem gegebenen Array arr[] mit n Elementen eine Funktion, um ein gegebenes Element x in arr[] zu suchen.

Abbildung 1: Ein Codebeispiel, das die Implementierung des linearen Suchalgorithmus zeigt

Quelle

Lineare Suchalgorithmen können in mehreren Programmiersprachen verwendet werden.

1. Lineare Suche in Python

Abbildung 2: Ein Codebeispiel, das einen linearen Suchalgorithmus in der Sprache Python zeigt

Quelle

Ausgabe: Element ist bei Index 3 vorhanden

2. Lineare Suche in C

Abbildung 3: Ein Codebeispiel, das einen linearen Suchalgorithmus in der Sprache C zeigt

Quelle

Ausgabe : Element ist bei Index 3 vorhanden

3. Lineare Suche in der Datenstruktur

Pseudocode für ein lineares Suchproblem in der Datenstruktur ist

Abbildung 4: Der Pseudocode für den linearen Suchalgorithmus

Quelle

Binäre Suche

Die binäre Suche ist ein Algorithmus zum Suchen von Elementen in einem Array von Elementen. Im Vergleich zum linearen Suchalgorithmus wird der binäre Suchalgorithmus auf eine sortierte Liste von Daten angewendet.

Der binäre Suchalgorithmus umfasst die folgenden Schritte

• Vergleich des zu suchenden Elements mit dem Element aus der Mitte der Liste oder des Arrays.
• Wenn das Element mit dem Element aus der Liste übereinstimmt, wird der Index des mittleren Elements zurückgegeben.
• Wenn keine Übereinstimmung zurückgegeben wird, wird geprüft, ob das Element größer oder kleiner als das Element in der Mitte ist.
• Für ein Element mit größerem Wert als das mittlere Element wird die Suche auf der rechten Seite des Arrays durchgeführt.
• Wenn das Element einen geringeren Wert als das mittlere Element hat, wird die Suche auf ähnliche Weise auf der linken Seite der Liste fortgesetzt.

Daher wird die binäre Suche am besten angewendet, wenn die Daten eine große Anzahl von Stabelementen in sortierter Weise enthalten. Dies macht es für den Suchalgorithmus erforderlich, dass die Liste/das Array sortiert werden sollte.

Merkmale der binären Suche

• Der binäre Suchalgorithmus ist nützlich, um eine große Anzahl von Elementen in einem Array zu durchsuchen.
• Der binäre Suchalgorithmus hat eine Zeitkomplexität von O(logn).
• Die Implementierung eines binären Suchalgorithmus ist einfach.

Binärer Suchalgorithmus

• Algorithmus Binary_Search(list, item)
• Setzen Sie L auf 0 und R auf n: 1
• wenn L > R, dann endet Binary_Search als nicht erfolgreich
• anders
• Setzen Sie m (die Position im mittleren Element) auf den Boden von (L + R) / 2
• wenn Am < T, setze L auf m + 1 und gehe zu Schritt 3
• wenn Am > T, setze R auf m: 1 und gehe zu Schritt 3
• Nun, Am = T,
• die Suche ist abgeschlossen; Rückkehr (m)

Fazit

In diesem Artikel haben wir uns angesehen, was ein linearer Suchalgorithmus ist, und auch im Detail untersucht, wie man mit dem linearen Suchalgorithmus nach einem bestimmten Element aus einer Liste sucht. Schließlich haben wir auch gesehen, wie wir den linearen Suchalgorithmus mit Python 3 als Sprache praktisch implementieren und unsere gewünschte Ausgabe erhalten können.

Wenn Sie sich für Data Science interessieren, müssen Sie sich das Executive PG Program in Data Science von IIIT-B und upGrad ansehen, das sorgfältig für Berufstätige ausgearbeitet wurde und zahlreiche Fallstudien, praktische Workshops, 1-zu-1-Mentoring und bietet viel mehr.