Die Entwicklung einer Suchfunktion stellt stets eine Herausforderung dar, ist aber keineswegs unüberwindbar.
Im Alltag suchen wir nicht nach einem festen Schema. Wir wenden uns intuitiv den Orten zu, an denen wir das Gesuchte vermuten. Dabei folgen wir meist keinem vorgegebenen Muster.
Lässt sich dieses Vorgehen auch in der Welt der Programmierung anwenden?
Nein, in Programmen benötigen wir ein klares Muster, um Daten zu durchsuchen. Dieser Artikel beleuchtet verschiedene Suchalgorithmen, die unterschiedlichen Mustern folgen.
Es existiert eine Vielzahl von Algorithmen in der Programmierung. Wir werden uns in diesem Beitrag auf die wichtigsten und gängigsten konzentrieren. Mit diesem Wissen werden Ihnen andere Algorithmen leichtfallen.
In diesem Artikel bezieht sich die Suche auf das Auffinden eines bestimmten Elements innerhalb eines Arrays.
Lassen Sie uns diese Algorithmen nun genauer betrachten.
Lineare Suche
Wie der Name bereits andeutet, verfolgt der lineare Suchalgorithmus ein lineares Muster, um die Elemente in einem Array zu durchsuchen. Der Algorithmus beginnt am Anfang des Arrays und bewegt sich bis zum Ende, bis das gesuchte Element gefunden wird. Sobald das Element gefunden ist, wird die Ausführung des Programms beendet.
Um den Algorithmus besser zu verstehen, werden wir die lineare Suche anhand von anschaulichen Beispielen verdeutlichen.
Bei genauer Betrachtung des Suchmusters fällt auf, dass die Laufzeit des Programms im ungünstigsten Fall O(n) beträgt. Bei der Analyse von Algorithmen betrachten wir in der Regel die Worst-Case-Zeitkomplexität. Daher beträgt die Zeitkomplexität dieses Algorithmus O(n).
Betrachten wir nun die Implementierung der linearen Suche.
Implementierung der linearen Suche
Nachdem Sie nun ein grundlegendes Verständnis der linearen Suche erlangt haben, ist es an der Zeit, selbst aktiv zu werden. Sehen wir uns zunächst die Schritte zur Implementierung an. Anschließend können Sie versuchen, den Code selbst zu schreiben. Keine Sorge, falls es nicht sofort klappt; ich werde Ihnen den Code im Anschluss zur Verfügung stellen.
Hier sind die Schritte zur Implementierung der linearen Suche:
- Initialisieren Sie ein Array mit Elementen (Ihre Glückszahlen).
- Erstellen Sie eine Funktion namens `search_element`, die drei Argumente akzeptiert: das Array, die Länge des Arrays und das zu suchende Element.
- `search_element(arr, n, element)`:
- Iterieren Sie durch das Array.
- Überprüfen Sie, ob das aktuelle Element mit dem gesuchten Element übereinstimmt.
- Falls ja, geben Sie `True` zurück.
- Wenn die Ausführung der Funktion nach Durchlaufen der gesamten Schleife immer noch aktiv ist, ist das Element nicht im Array enthalten. Geben Sie in diesem Fall `False` zurück.
- Iterieren Sie durch das Array.
- Geben Sie eine entsprechende Meldung aus, die auf dem Rückgabewert der Funktion `search_element` basiert.
Versuchen Sie nun, den Code mithilfe der oben genannten Schritte zu schreiben.
Haben Sie die Implementierung der linearen Suche abgeschlossen? Ich hoffe doch. Wenn Sie fertig sind, vergleichen Sie es mit dem folgenden Code.
Wenn Sie es nicht geschafft haben, ist das kein Problem. Sehen Sie sich den folgenden Code an und erfahren Sie, wie wir die Implementierung vorgenommen haben. Sie werden es im Handumdrehen verstehen.
## Suchfunktion def search_element(arr, n, element): ## Iteration durch das Array for i in range(n): ## Überprüfung, ob aktuelles Element mit gesuchtem Element übereinstimmt if arr[i] == element: ## Rückgabe von True bei Übereinstimmung return True ## Element wurde nicht gefunden, daher gelangt die Ausführung hierher return False if __name__ == '__main__': ## Initialisieren von Array, Länge und zu suchendem Element 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, "wurde gefunden") else: print(element_to_be_searched, "wurde nicht gefunden")
Führen Sie das Programm zuerst mit einem Element aus, das im Array vorhanden ist. Führen Sie es anschließend mit einem Element aus, das nicht im Array vorhanden ist.
Die Zeitkomplexität der linearen Suche beträgt O(n).
Können wir diese Zeitkomplexität mit anderen Mustern noch weiter reduzieren?
Ja, das ist möglich. Sehen wir uns das an.
Binäre Suche
Die binäre Suche untersucht immer das mittlere Element des Arrays. Dieser Algorithmus funktioniert nur mit sortierten Arrays.
Die binäre Suche iteriert durch das Array und prüft, ob das mittlere Element das gesuchte Element ist. Wenn ja, wird das Programm beendet. Andernfalls wird der Suchbereich in jeder Iteration halbiert: Ist das mittlere Element kleiner als das gesuchte Element, wird der linke Teil des Arrays bei der Suche ausgelassen. Ist es größer, wird der rechte Teil ausgelassen.
Dadurch ist die Anzahl der erforderlichen Überprüfungen deutlich geringer als bei der linearen Suche.
Abbildungen können das Prinzip der binären Suche besser veranschaulichen. Betrachten wir diese nun.
Die Zeitkomplexität der binären Suche beträgt O(log n), da sich der Suchbereich bei jeder Iteration halbiert. Diese Reduktion erfolgt exponentiell.
Implementierung der binären Suche
Zunächst sehen wir uns die Schritte zur Implementierung der binären Suche an und anschließend den Code. Hier sind die Schritte:
- Initialisieren Sie das Array mit Elementen (Ihre Glückszahlen).
- Erstellen Sie eine Funktion namens `search_element`, die drei Argumente akzeptiert: ein sortiertes Array, die Länge des Arrays und das zu suchende Element.
- `search_element(sorted_arr, n, element)`:
- Initialisieren Sie eine Indexvariable `i` für die Iteration durch das Array.
- Initialisieren Sie zwei Variablen, um den Suchbereich des Arrays zu verfolgen. Wir nennen sie hier `start` und `end`, da sie Indizes angeben.
- Iterieren Sie so lange, wie `i` kleiner als die Länge des Arrays ist.
- Berechnen Sie den mittleren Index des Suchbereichs anhand von `start` und `end`. Das ist `(start + end) // 2`.
- Überprüfen Sie, ob das Element am mittleren Index mit dem gesuchten Element übereinstimmt.
- Falls ja, geben Sie `True` zurück.
- Ist das Element am mittleren Index kleiner als das gesuchte Element, setzen Sie den `start`-Index des Suchbereichs auf `Mitte + 1`.
- Ist das Element am mittleren Index größer als das gesuchte Element, setzen Sie den `end`-Index des Suchbereichs auf `Mitte – 1`.
- Erhöhen Sie den Array-Index `i`.
- Wenn die Ausführung nach Durchlaufen der gesamten Schleife immer noch aktiv ist, ist das Element nicht im Array enthalten. Geben Sie in diesem Fall `False` zurück.
- Geben Sie eine entsprechende Meldung aus, die auf dem Rückgabewert der Funktion `search_element` basiert.
Versuchen Sie, den Code analog zur Implementierung der linearen Suche zu schreiben.
…
Haben Sie den Code fertig?
Vergleichen Sie ihn mit dem folgenden Code. Wenn es nicht geklappt hat, keine Sorge: Erfahren Sie die Details der Implementierung mithilfe des folgenden Codes.
## Suchfunktion def search_element(sorted_arr, n, element): ## Array-Index für die Iteration i = 0 ## Variablen zur Verfolgung des Suchbereichs ## Initialisierung mit Start- und Endindizes start = 0 end = n - 1 ## Iteration durch das Array while i < n: ## Ermittlung des Index des mittleren Elements middle = (start + end) // 2 ## Überprüfung, ob das mittlere Element mit dem gesuchten Element übereinstimmt if sorted_arr[middle] == element: ## Rückgabe von True, da das Element im Array enthalten ist return True elif sorted_arr[middle] < element: ## Verschieben des Startindexes des Suchbereichs nach rechts start = middle + 1 else: ## Verschieben des Endindexes 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(element_to_be_searched, "wurde gefunden") else: print(element_to_be_searched, "wurde nicht gefunden")
Testen Sie den Code mit verschiedenen Fällen, sowohl mit Elementen, die im Array vorhanden sind, als auch mit Elementen, die nicht vorhanden sind.
Fazit
Die binäre Suche ist deutlich effizienter als die lineare Suche. Allerdings muss das Array für die binäre Suche sortiert sein, was bei der linearen Suche nicht erforderlich ist. Das Sortieren benötigt Zeit. Die Verwendung effizienter Sortieralgorithmen in Verbindung mit der binären Suche kann jedoch eine gute Kombination darstellen.
Sie haben nun ein solides Verständnis der gebräuchlichsten Suchalgorithmen in Python.
Informieren Sie sich als Nächstes über einige der beliebtesten Self-Hosted-Suchsoftware.
Viel Spaß beim Programmieren! 🙂 🧑💻