Die Implementierung einer Suche ist immer eine Herausforderung, aber nicht unmöglich.
Im wirklichen Leben werden wir ohne Muster suchen. Wir gehen einfach zu den Orten, an denen wir glauben, dass es platziert werden könnte. In den meisten Fällen folgen wir keinem Muster.
Funktioniert das Gleiche auch in der Welt des Programmierens?
NEIN! Es muss ein bestimmtes Muster für die Suche nach Dingen in Programmen geben. In diesem Artikel werden wir uns einige Algorithmen ansehen, die unterschiedlichen Suchmustern folgen.
Es gibt mehrere Algorithmen, die wir in der Welt der Programmierung 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.
Die Suche bezieht sich auf Suche nach einem Element im Array In diesem Artikel.
Schauen wir sie uns einzeln an.
Lineare Suche
Der Name lässt vermuten, dass die linearer Suchalgorithmus Folge dem linear Muster um nach Elementen in einem Array zu suchen. Der Algorithmus beginnt mit der Suche nach dem Element am Anfang des Arrays und geht bis zum Ende, bis er das Element findet. Stoppt die Programmausführung, wenn das erforderliche Element gefunden wird.
Lassen Sie uns das veranschaulichen lineare Suchalgorithmen mit einigen coolen Illustrationen zum besseren Verständnis des Algorithmus.
Wenn Sie sich das Suchmuster genau ansehen, werden Sie feststellen, dass die Ausführung des Programms einige Zeit in Anspruch nimmt In) drin der schlimmste Fall. Wir müssen die zeitliche Komplexität der zu analysierenden Algorithmen im ungünstigsten Fall berücksichtigen. Daher beträgt die zeitliche Komplexität des Algorithmus In).
Schauen 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, sich mit etwas Code die Hände schmutzig zu machen. Schauen wir uns zunächst die Schritte zur Implementierung der linearen Suche an. Dann versuchen Sie es zu codieren. Machen Sie sich keine Sorgen, auch wenn Sie es nicht können. Ich werde Ihnen den Code später zur Verfügung stellen.
Schauen wir uns die Schritte zur Implementierung des linearen Suchalgorithmus an.
- Initialisieren Sie ein Array von Elementen (Ihre Glückszahlen).
- Schreiben Sie eine Funktion namens search_item, das drei Argumente akzeptiert: Array, Array-Länge und zu suchendes Element.
- search_item(arr, n, item):
- Iterieren Sie über das angegebene Array.
- Überprüfen Sie, ob das aktuelle Element dem erforderlichen Element entspricht.
- Wenn ja, dann komm zurück WAHR.
- Wenn sich die Ausführung nach Abschluss der Schleife noch in der Funktion befindet, ist das Element nicht im Array vorhanden. Deshalb kehre ich zurück Gefälscht.
- Iterieren Sie über das angegebene Array.
- Drucken Sie die Nachricht basierend auf dem Rückgabewert der Funktion search_item.
Schreiben Sie abschließend den Code mithilfe der oben genannten Schritte, um den linearen Suchalgorithmus zu implementieren.
Haben Sie die Implementierung des linearen Suchalgorithmus abgeschlossen? Ich hoffe es. Wenn der Vorgang abgeschlossen ist, überprüfen Sie ihn mit dem folgenden Code.
Wenn Sie es nicht abgeschlossen haben, machen Sie sich keine Sorgen. Sehen Sie sich den Code unten an und erfahren Sie, wie wir ihn implementieren. Sie werden es ohne großen Aufwand erreichen.
## 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 zunächst das Programm mit einem Element aus, das im Array vorhanden ist. Und führen Sie es dann mit einem Element aus, das nicht im Array vorhanden ist.
Die zeitliche Komplexität des linearen Suchalgorithmus beträgt In).
Können wir es mit verschiedenen Mustern etwas weiter eingrenzen?
Wenn wir können. Mal sehen.
Binäre Suche
Die binärer Suchalgorithmus prüft immer das mittlere Element des Arrays. Dieser Algorithmus sucht nach dem Element in a sortiertes Array.
Die binärer Suchalgorithmus Es durchläuft das Array und überprüft das mittlere Element. Wenn es es findet, stoppt es das Programm. Andernfalls, wenn das mittlere Element kleiner als das erforderliche Element ist, wird der linke Teil des mittleren Elementarrays bei der Suche übersprungen. Andernfalls, wenn das mittlere Element größer als das erforderliche Element ist, wird der rechte Teil des mittleren Elementarrays bei der Suche übersprungen.
Bei jeder Iteration reduziert der binäre Suchalgorithmus den Suchbereich für das Element. Daher ist die Anzahl der Prüfungen geringer als die Anzahl der im linearen Suchalgorithmus durchgeführten Prüfungen.
Die Abbildungen helfen uns, das besser zu verstehen binärer Suchalgorithmus. Lassen Sie uns sie überprüfen.
Die zeitliche Komplexität des binären Suchalgorithmus beträgt O (Datensatz n). Bei jeder Iteration wird die Länge des Suchbereichs um die Hälfte reduziert. Es nimmt exponentiell ab.
Implementierung der binären Suche
Wir werden uns zunächst die Schritte zur Implementierung des binären Suchalgorithmus und dann den Code ansehen. Schauen wir uns die Schritte zum Abschluss der Implementierung des binären Suchalgorithmus an.
- Initialisieren Sie das Array mit Elementen (Ihren Glückszahlen)
- Schreiben Sie eine Funktion namens search_item, das drei Argumente akzeptiert: sortiertes Array, Array-Länge und zu suchendes Element.
- search_item(arr_sort, n, item):
- Indexvariable initialisieren Yo für Array-Iteration.
- Initialisieren Sie dann zwei Variablen, um den Suchbereich des Arrays beizubehalten. Hier nennen wir sie so Anfang Und Finale wie die Indizes zeigen.
- Iterieren bis Yo ist kleiner als die Länge des Arrays.
- Berechnen Sie den durchschnittlichen Index des Suchbereichs mithilfe von Anfang Und Finale Werte. Das wird sein (Anfang + Ende) // 2.
- Überprüfen Sie, ob das mittlere indizierte Element des Suchbereichs mit dem erforderlichen Element übereinstimmt oder nicht.
- Wenn ja, dann komm zurück WAHR.
- Andernfalls, wenn das mittlere indizierte Element kleiner als das erforderliche Element ist, verschieben Sie das Anfang Suchbereichsindex für mittel + 1.
- Andernfalls, wenn das mittlere indizierte Element größer als das erforderliche Element ist, verschieben Sie es Finale Suchbereichsindex für mittel – 1.
- Erhöht den Index des Arrays. Yo.
- Wenn sich die Ausführung nach Abschluss der Schleife noch in der Funktion befindet, ist das Element nicht im Array vorhanden. Deshalb kehre ich zurück Gefälscht.
- Drucken Sie die Nachricht basierend auf dem Rückgabewert der Funktion search_item.
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 Angst; 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 ist und in einigen Fällen nicht.
Abschluss
Die binärer Suchalgorithmus Es ist viel effizienter als linearer Suchalgorithmus. Wir müssen das Array für den binären Suchalgorithmus sortieren, dies ist beim linearen Suchalgorithmus nicht der Fall. Das Sortieren nimmt einige Zeit in Anspruch. Die Verwendung effizienter Sortieralgorithmen lässt sich jedoch gut mit dem binären Suchalgorithmus kombinieren.
Jetzt haben Sie ein gutes Verständnis der am häufigsten verwendeten Algorithmen in Python.
Entdecken Sie unten einige der beliebten selbst gehosteten Suchprogramme.
Viel Spaß beim Codieren 🙂 🧑💻
