Implementierungen von Suchalgorithmen in Python

Die Implementierung einer Suche ist immer eine Herausforderung, aber nicht unmöglich

Im wirklichen Leben werden wir nicht nach einem bestimmten Muster suchen. Wir gehen einfach an die Orte, von denen wir denken, dass sie sich dort befinden könnten. In den meisten Fällen folgen wir keinem Muster

Funktioniert das auch in der Welt der Programmierung?

Nein! Es muss ein Muster geben, um Dinge in Programmen zu suchen. In diesem Artikel werden wir uns einige Algorithmen ansehen, die verschiedenen Mustern für die Suche folgen

Es gibt zahlreiche Algorithmen, die wir in der Welt der Programmierung finden können. Wir werden in diesem Artikel die wichtigsten und am häufigsten verwendeten Algorithmen besprechen. Die übrigen Algorithmen werden Sie mühelos erlernen können

Mit Suchen ist in diesem Artikel die Suche nach einem Element in einem Array gemeint

Sehen wir uns die Algorithmen nacheinander an

Lineare Suche

Wie der Name schon sagt, folgt der lineare Suchalgorithmus einer linearen Muster, um die Elemente in einem Array zu suchen. Der Algorithmus beginnt die Suche nach einem Element am Anfang des Arrays und bewegt sich zum Ende, bis er das Element gefunden hat. Er hält die Ausführung des Programms an, wenn er das gewünschte Element gefunden hat

Lassen Sie uns die lineare Suchalgorithmen mit einigen coolen Illustrationen veranschaulichen, um den Algorithmus besser zu verstehen

Wenn Sie das Suchmuster genau beobachten, werden Sie feststellen, dass die Zeit für die Ausführung des Programms im schlimmster Fall O(n) Wir müssen die Worst-Case-Zeitkomplexität der zu analysierenden Algorithmen berücksichtigen. Daher ist die Zeitkomplexität des Algorithmus O(n)

Schauen wir uns nun die Implementierung des linearen Suchalgorithmus an

Implementierung der linearen Suche

Jetzt haben Sie ein gutes Verständnis des linearen Suchalgorithmus. Jetzt ist es an der Zeit, sich die Hände mit etwas Code schmutzig zu machen. Sehen wir uns zunächst die Schritte zur Implementierung der linearen Suche an. Dann versuchen Sie es, Sie zu codieren. Machen Sie sich keine Sorgen, auch wenn Sie es nicht können; ich werde Ihnen den Code nachher zur Verfügung stellen.

Schauen wir uns die Schritte zur Implementierung des linearen Suchalgorithmus an

Initialisieren Sie ein Array mit Elementen (Ihre Glückszahlen).
Schreiben Sie eine Funktion namens such_element, die drei Argumente akzeptiert: array, Länge des Arrays und das zu suchende Element.
suche_element(array, n, element)
- Iteriert über das angegebene Array
  - Prüfen Sie, ob das aktuelle Element gleich dem gewünschten Element ist.
  - Wenn ja, dann geben Sie Wahr zurück.
- Befindet sich die Ausführung nach Abschluss der Schleife noch in der Funktion, dann ist das Element nicht im Array vorhanden. Geben Sie daher Falsch zurück.
Drucken Sie die Nachricht auf der Grundlage des Rückgabewerts der Funktion such_element.

Schreiben Sie schließlich den Code mit Hilfe der oben genannten Schritte, um den linearen Suchalgorithmus zu implementieren

Haben Sie die Implementierung des linearen Suchalgorithmus abgeschlossen? Ich hoffe ja. Wenn Sie es geschafft haben, dann überprüfen Sie es mit dem folgenden Code

Wenn Sie es nicht geschafft haben, machen Sie sich keine Sorgen. Sehen Sie sich den folgenden Code an und lernen Sie, wie wir ihn implementiert haben. Sie werden es ohne viel Mühe schaffen

## Suchfunktion
def search_element(arr, n, element):

## Iterieren durch das Array
for i in range(n):

## Überprüfen des aktuellen Elements mit dem gewünschten Element
if arr[i] == element:
## Rückgabe von True bei Übereinstimmung
return True

## Element wird nicht gefunden, daher kommt die Ausführung hier
return False


if __name__ == '__main__':
	## Initialisierung des Arrays, der Länge und des zu suchenden Elements
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n = 10
element_to_be_searched = 6
# element_to_be_searched = 11

if search_element(arr, n, element_to_be_searched):
		print(zu_suchendes_Element, "wird gefunden")
else:
print(zu_suchendes_Element, "wird nicht gefunden")

Führen Sie das Programm zunächst mit einem Element aus, das im Array vorhanden ist. Als nächstes führen Sie es mit einem Element aus, das nicht im Array vorhanden ist

Die Zeitkomplexität des linearen Suchalgorithmus ist O(n)

Können wir sie mit verschiedenen Mustern noch weiter reduzieren?

Ja, das können wir. Schauen wir es uns an

Binäre Suche

Der binärer Suchalgorithmus prüft immer das mittlere Element des Arrays. Dieser Algorithmus durchsucht das Element in einem sortiertes Array

Der binärer Suchalgorithmus iteriert über das Array und prüft das mittlere Element, wenn es gefunden wird, wird das Programm angehalten. Andernfalls, wenn das mittlere Element kleiner als das gewünschte Element ist, wird der linke Teil des Arrays ab dem mittleren Element von der Suche ausgeschlossen. Andernfalls, wenn das mittlere Element größer als das gewünschte Element ist, wird der rechte Teil des Arrays ab dem mittleren Element von der Suche ausgeschlossen.

Bei jeder Iteration verkleinert der binäre Suchalgorithmus den Bereich, in dem das Element gesucht wird. Die Anzahl der Überprüfungen ist auch geringer als die Anzahl der Überprüfungen beim linearen Suchalgorithmus.

Illustrationen helfen uns, den binärer Suchalgorithmus besser zu verstehen. Schauen wir sie uns an

Die Zeitkomplexität des binären Suchalgorithmus ist O(log n). Bei jeder Iteration verringert sich die Länge des Suchbereichs um die Hälfte. Sie nimmt exponentiell ab

Implementierung der binären Suche

Zunächst sehen wir uns die Schritte zur Implementierung des binären Suchalgorithmus und dann den Code an. Sehen wir uns nun die Schritte zur Implementierung des binären Suchalgorithmus an

Initialisieren Sie das Array mit Elementen (Ihre Glückszahlen)
Schreiben Sie eine Funktion namens such_element, die drei Argumente akzeptiert: sortiertes Array, Länge des Arrays und zu suchendes Element.
suche_element(sort_arr, n, element)
- Initialisieren Sie die Indexvariable i für die Iteration des Arrays.
- Als nächstes initialisieren Sie zwei Variablen, um den Suchbereich des Arrays zu erhalten. Hier nennen wir sie Start und Ende , da sie Indizes angeben.
- Iterieren Sie, bis i kleiner als die Länge des Arrays ist
  - Berechnen Sie den mittleren Index des Suchbereichs anhand der Start- und Endwerte . Das ist dann (Anfang Ende) // 2.
  - Prüfen Sie, ob das mittlere indizierte Element aus dem Suchbereich gleich dem gewünschten Element ist oder nicht.
  - Wenn ja, dann geben Sie Wahr zurück.
  - Andernfalls, wenn das mittlere indizierte Element kleiner ist als das gewünschte Element, dann verschieben Sie den Startindex des Suchbereichs auf Mitte 1 .
  - Andernfalls, wenn das mittlere indizierte Element größer ist als das gewünschte Element, dann verschieben Sie den Endindex des Suchbereichs auf Mitte - 1.
  - Erhöhen Sie den Index des Arrays i.
- Wenn sich die Ausführung nach Beendigung der Schleife noch in der Funktion befindet, ist das Element nicht im Array vorhanden. Geben Sie daher Falsch zurück.
Drucken Sie die Nachricht auf der Grundlage des Rückgabewerts der Funktion such_element.

Versuchen Sie, den Code ähnlich wie bei der Implementierung des linearen Suchalgorithmus zu schreiben.

Haben Sie den Code erhalten?

Ja, vergleichen Sie ihn mit dem unten stehenden Code. Nein, machen Sie sich keine Sorgen; verstehen Sie die Implementierung mit dem unten stehenden Code

## Suchfunktion
def search_element(sort_arr, n, element):

## Array-Index für Iteration
i = 0

## Variablen zur Verfolgung des Suchbereichs
## Initialisierung mit Start- und End-Index
start = 0
end = n - 1

## Iteration über das Array
while i < n:
		## Ermitteln des Index des mittleren Elements
middle = (start end) // 2

## Überprüfen des mittleren Elements mit dem erforderlichen Element
if sorted_arr<x>[middle]</x> == element:
## Rückgabe von True, da das Element im Array ist
return True
elif sorted_arr<x>[middle]</x> < element:
			## Verschieben des Startindex des Suchbereichs nach rechts
start = middle 1
else:
## Verschieben des Endindex des Suchbereichs nach links
end = middle - 1
i = 1
return False


if __name__ == '__main__':
	## Initialisierung des Arrays, der Länge und des zu suchenden Elements
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n = 10
element_to_be_searched = 9
# element_to_be_searched = 11

if search_element(arr, n, element_to_be_searched):
		print(zu_suchendes_Element, "wird gefunden")
else:
print(zu_suchendes_Element, "wird nicht gefunden")

Testen Sie den Code mit verschiedenen Fällen, in denen das Element in einigen Fällen vorhanden und in anderen nicht vorhanden ist

Schlussfolgerung

Der binärer Suchalgorithmus ist wesentlich effizienter als der lineare Suchalgorithmus. Beim binären Suchalgorithmus müssen wir das Array sortieren, was beim linearen Suchalgorithmus nicht der Fall ist. Das Sortieren nimmt einige Zeit in Anspruch. Aber die Verwendung effizienter Algorithmen zum Sortieren bildet eine gute Kombination mit dem binären Suchalgorithmus

Jetzt kennen Sie die am häufigsten verwendeten Algorithmen in Python

Als Nächstes werden Sie einige der beliebtesten selbst gehostete Suchprogramme kennen lernen

Viel Spaß beim Programmieren 🙂 🧑‍💻