Implementierungen von Suchalgorithmen in Python • 1techpc.de

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

Im wirklichen Leben werden wir nach keinem Muster suchen. Wir gehen einfach zu den Orten, an denen wir denken, dass es platziert werden könnte. Wir folgen in den meisten Fällen keinem Muster.

Funktioniert das auch in der Programmierwelt?

Nein! Es muss ein Muster geben, um Dinge in Programmen zu durchsuchen. In diesem Artikel werden wir einige Algorithmen sehen, die unterschiedlichen Suchmustern folgen.

Es gibt mehrere Algorithmen, die wir in der Programmierwelt finden können. Wir werden in diesem Artikel die wichtigsten und am häufigsten verwendeten Algorithmen diskutieren. Und der Rest der Algorithmen wird für Sie ein Kinderspiel sein.

Suchen bezieht sich auf das Suchen eines Elements im Array in diesem Artikel.

Sehen wir sie uns nacheinander an.

Inhaltsverzeichnis

Lineare Suche

Der Name deutet darauf hin, dass der lineare Suchalgorithmus dem linearen Muster folgt, um die Elemente in einem Array zu durchsuchen. Der Algorithmus beginnt mit der Suche nach dem Element am Anfang des Arrays und bewegt sich zum Ende, bis er das Element findet. Es stoppt die Ausführung des Programms, wenn es das erforderliche Element findet.

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

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

Sehen wir uns die Implementierung des linearen Suchalgorithmus an.

Implementierung der linearen Suche

Jetzt haben Sie ein gutes Verständnis des linearen Suchalgorithmus. Es ist Zeit, unsere Hände mit etwas Code schmutzig zu machen. Sehen wir uns zuerst die Schritte zum Implementieren der linearen Suche an. Dann versuchst du es zu codieren. Machen Sie sich keine Sorgen, auch wenn Sie es nicht können; Den Code schicke ich dir danach.

Sehen wir uns die Schritte zum Implementieren des linearen Suchalgorithmus an.

Initialisieren Sie ein Array von Elementen (Ihre Glückszahlen).
Schreiben Sie eine Funktion namens search_element, die drei Argumente akzeptiert, Array, Länge des Arrays und zu durchsuchendes Element.
such_element(arr, n, element):
- Iteriere über das angegebene Array.
  - Prüfen Sie, ob das aktuelle Element gleich dem erforderlichen Element ist.
  - Wenn ja, dann True zurückgeben.
- Wenn die Ausführung nach Abschluss der Schleife immer noch in der Funktion erfolgt, ist das Element nicht im Array vorhanden. Geben Sie daher False zurück.
Gibt die Nachricht basierend auf dem Rückgabewert der Funktion search_element aus.

Wie deaktiviere ich AWS EC2-Metadaten?

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

Haben Sie die Implementierung des linearen Suchalgorithmus abgeschlossen? Hoffentlich. Wenn Sie fertig sind, überprüfen Sie es mit dem folgenden Code.

Wenn Sie es nicht abgeschlossen haben, machen Sie sich keine Sorgen; Sehen Sie sich den folgenden Code an und erfahren Sie, wie wir ihn implementiert haben. Sie werden es ohne großen Aufwand bekommen.

## searching function
def search_element(arr, n, element):

	## iterating through the array
	for i in range(n):

		## checking the current element with required element
		if arr[i] == element:
			## returning True on match
			return True

	## element is not found hence the execution comes here
	return False


if __name__ == '__main__':
	## initializing the array, length, and element to be searched
	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(element_to_be_searched, "is found")
	else:
		print(element_to_be_searched, "is not found")

Führen Sie zuerst das Programm mit einem Element aus, das im Array vorhanden ist. Führen Sie es als nächstes mit einem Element aus, das nicht im Array vorhanden ist.

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

Können wir es mit anderen Mustern noch ein bisschen weiter reduzieren?

Ja, wir können. Mal sehen.

Binäre Suche

Der binäre Suchalgorithmus überprüft immer das mittlere Element des Arrays. Dieser Algorithmus sucht das Element in einem sortierten Array.

Der binäre Suchalgorithmus iteriert über das Array und überprüft das mittlere Element, wenn es gefunden wird, und stoppt dann das Programm. Andernfalls, wenn das mittlere Element kleiner als das erforderliche Element ist, wird der linke Teil des Arrays vom mittleren Element bei der Suche ausgelassen. Andernfalls, wenn das mittlere Element größer als das erforderliche Element ist, wird der rechte Teil des Arrays vom mittleren Element bei der Suche ausgelassen.

So finden und senden Sie GIFs in Slack

Bei jeder Iteration schneidet der binäre Suchalgorithmus den Bereich zum Suchen des Elements ab. Die Anzahl der Überprüfungen ist also geringer als die Anzahl der Überprüfungen, die im linearen Suchalgorithmus durchgeführt werden.

Abbildungen helfen uns, den binären Suchalgorithmus besser zu verstehen. Lassen Sie uns sie überprüfen.

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. Es nimmt exponentiell ab.

Implementierung der binären Suche

Zuerst sehen wir die Schritte zur Implementierung des binären Suchalgorithmus und dann den Code. Sehen wir uns die Schritte zum Abschließen der Implementierung des binären Suchalgorithmus an.

Initialisieren Sie das Array mit Elementen (Ihren Glückszahlen)
Schreiben Sie eine Funktion namens search_element, die drei Argumente akzeptiert, ein sortiertes Array, die Länge des Arrays und das zu durchsuchende Element.
search_element(sorted_arr, n, element):
- Initialisieren Sie die Indexvariable i für die Array-Iteration.
- Initialisieren Sie als Nächstes zwei Variablen, um den Suchbereich des Arrays beizubehalten. Hier nennen wir sie als Anfang und Ende, da sie Indizes angeben.
- Iteriere, bis das i kleiner als die Länge des Arrays ist.
  - Berechnen Sie den mittleren Index des Suchbereichs anhand der Start- und Endwerte. Das wird (Start + Ende) // 2 sein.
  - Überprüfen Sie, ob das mittlere indizierte Element aus dem Suchbereich gleich dem erforderlichen Element ist oder nicht.
  - Wenn ja, dann True zurückgeben.
  - Andernfalls, wenn das mittlere indizierte Element kleiner als das erforderliche Element ist, verschieben Sie den Startindex des Suchbereichs auf Mitte + 1.
  - Andernfalls, wenn das mittlere indizierte Element größer als das erforderliche Element ist, verschieben Sie den Endindex des Suchbereichs auf Mitte – 1.
  - Erhöhen Sie den Index des Arrays i.
- Wenn die Ausführung nach Abschluss der Schleife immer noch in der Funktion erfolgt, ist das Element nicht im Array vorhanden. Geben Sie daher False zurück.
Gibt die Nachricht basierend auf dem Rückgabewert der Funktion search_element aus.

So aktualisieren Sie auf Ubuntu 21.10

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

…

Hast du den Code bekommen?

Ja, vergleichen Sie es mit dem folgenden Code. Nein, keine Sorge; Verstehen Sie die Implementierung mit dem folgenden Code.

## searching function
def search_element(sorted_arr, n, element):

	## array index for iteration
	i = 0

	## variables to track the search area
	## initializing them with start and end indexes
	start = 0
	end = n - 1

	## iterating over the array
	while i < n:
		## getting the index of the middle element
		middle = (start + end) // 2

		## checking the middle element with required element
		if sorted_arr[middle] == element:
			## returning True since the element is in the array
			return True
		elif sorted_arr[middle] < element:
			## moving the start index of the search area to right
			start = middle + 1
		else:
			## moving the end index of the search area to left
			end = middle - 1
		i += 1
	return False


if __name__ == '__main__':
	## initializing the array, length, and element to be searched
	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(element_to_be_searched, "is found")
	else:
		print(element_to_be_searched, "is not found")

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

Fazit

Der binäre Suchalgorithmus ist viel effizienter als der lineare Suchalgorithmus. Wir müssen das Array für den binären Suchalgorithmus sortieren, was beim linearen Suchalgorithmus nicht der Fall ist. Das Sortieren dauert einige Zeit. Die Verwendung effizienter Sortieralgorithmen bildet jedoch eine gute Kombination mit dem binären Suchalgorithmus.

Jetzt haben Sie gute Kenntnisse über die am häufigsten verwendeten Algorithmen in Python.

Informieren Sie sich als Nächstes über einige der beliebten selbst gehosteten Suchsoftware.

Viel Spaß beim Programmieren 🙂 🧑‍💻