Suchen in der Datenstruktur: Erklärung verschiedener Suchmethoden
Veröffentlicht: 2021-05-03Das Kommunikationsnetz dehnt sich aus, und so nutzen die Menschen das Internet! Unternehmen werden für ein effizientes Management digitalisiert. Die im Internet generierten Daten steigen und damit werden die Datensätze immer komplexer. Es ist wichtig, die Daten sorgfältig und effizient zu organisieren, zu verwalten, darauf zuzugreifen und zu analysieren, eine Datenstruktur ist die hilfreichste Technik, und der Artikel konzentriert sich darauf!
Inhaltsverzeichnis
Datenstruktur
Datenstrukturen sind in der Informatik die Grundlage für abstrakte Datentypen (ADT), wobei ADT die logische Form des Datentyps sind. Das physikalische Layout des Datentyps wird über die Datenstruktur implementiert. Unterschiedliche Datenstrukturtypen werden für unterschiedliche Arten von Anwendungen verwendet; einige sind auf bestimmte Aufgaben spezialisiert.
Die Datenstruktur ist eine Sammlung von Datenwerten und Beziehungen zwischen ihnen, Operationen und Funktionen, die auf die Daten anwendbar sind. Es hilft bei der Organisation, Verwaltung und Speicherung von Daten in einem bestimmten Format. Somit können Benutzer einfach auf die Daten zugreifen und diese effizient ändern.
Datenstrukturen helfen bei der Verwaltung großer Datenmengen, z. B. umfangreicher Datenbanken. Effiziente Algorithmen werden basierend auf effizienten Datenstrukturen erstellt. Neben der effizienten Speicherung sind Datenstrukturen auch für das effiziente Abrufen von Informationen aus dem gespeicherten Speicher verantwortlich. Es enthält ein Array, eine verknüpfte Liste, einen Zeiger, Suchen, Stapeln, Diagramm, Warteschlange, Struktur, Programme, Sortieren und so weiter.
Der Artikel behandelt das Konzept der Suche in der Datenstruktur und seine Methoden. Zwei Beispiele von Algorithmen werden ausführlich erklärt, um das Konzept klar zu verstehen. Um weitere Kenntnisse, Fähigkeiten und Fachkenntnisse zu erwerben, stehen Online-Kurse zur Datenstruktur zur Verfügung, die am Ende des Artikels erwähnt werden.
Was ist die Suche in der Datenstruktur?
Der Vorgang des Auffindens der gewünschten Informationen aus der Menge von Elementen, die in Form von Elementen im Computerspeicher gespeichert sind, wird als "Suchen in einer Datenstruktur" bezeichnet. Diese Sätze von Elementen liegen in verschiedenen Formen vor, wie z. B. als Array, Baum, Diagramm oder verknüpfte Liste. Eine andere Möglichkeit, die Suche in der Datenstruktur zu definieren, besteht darin, das gewünschte Element mit bestimmten Merkmalen in einer Sammlung von Elementen zu lokalisieren.
Suchmethoden
Das Suchen in der Datenstruktur kann durch Implementieren von Suchalgorithmen erfolgen, um nach einem Element zu suchen oder es aus einer beliebigen Form einer gespeicherten Datenstruktur abzurufen. Diese Algorithmen werden basierend auf ihrer Art der Suchoperation kategorisiert, wie zum Beispiel:
- Sequentielle Suche
Das Array oder die Liste von Elementen wird sequentiell durchlaufen, während jede Komponente des Satzes geprüft wird.
Beispiel: Lineare Suche.
- Intervallsuche
Algorithmen, die explizit für die Suche in sortierten Datenstrukturen ausgelegt sind, werden in die Intervallsuche einbezogen. Die Effizienz dieser Algorithmen ist weitaus besser als lineare Suchalgorithmen.
Zum Beispiel binäre Suche, logarithmische Suche.
Diese Methoden werden basierend auf der Zeit untersucht, die ein Algorithmus benötigt, um ein Element zu suchen, das dem Suchbegriff in den Datensammlungen entspricht, und sind gegeben durch:
- Die bestmögliche Zeit
- Die durchschnittliche Zeit
- Die Worst-Case-Zeit
Die Hauptsorge gilt den Worst-Case-Zeiten, die zu garantierten Vorhersagen der Leistung des Algorithmus führen und im Vergleich zu Durchschnittszeiten auch einfach zu berechnen sind.
Zur Veranschaulichung von Beispielen und Konzepten in diesem Artikel werden „n“ Elemente in der Datenerfassung in einem beliebigen Datenformat betrachtet. Dominante Operationen werden verwendet, um die Analyse und den Algorithmusvergleich zu vereinfachen. Beim Suchen in einer Datenstruktur ist ein Vergleich eine dominante Operation, die mit O() bezeichnet und als „big-Oh“ oder „Oh“ ausgesprochen wird.
Es gibt zahlreiche Suchalgorithmen in einer Datenstruktur, wie z. B. lineare Suche, binäre Suche, Interpolationssuche, Sprungsuche, exponentielle Suche, Fibonacci-Suche, Unterlistensuche, die allgegenwärtige binäre Suche, unbegrenzte binäre Suche, rekursive Funktion für Teilstringsuche und rekursives Programm um ein Element linear im gegebenen Array zu suchen. Der Artikel beschränkt sich auf lineare und binäre Suchalgorithmen und deren Funktionsprinzipien.
Lassen Sie uns einen detaillierten Einblick in die lineare Suche und die binäre Suche in der Datenstruktur erhalten.
Lineare Suche
Der lineare Suchalgorithmus durchsucht nacheinander alle Elemente im Array. Die beste Ausführungszeit ist eins, während die schlechteste Ausführungszeit n ist, wobei n die Gesamtzahl der Elemente im Sucharray ist.
Es ist der einfachste Suchalgorithmus in der Datenstruktur und überprüft jedes Element in der Menge von Elementen, bis es bis zum Ende der Datenerfassung mit dem Suchelement übereinstimmt. Bei unsortierten Daten wird ein linearer Suchalgorithmus bevorzugt.
Die lineare Suche hat einige Komplexitäten, wie unten angegeben:
- Raumkomplexität
Die Platzkomplexität für die lineare Suche ist O(n), da sie keinen zusätzlichen Platz verwendet, wobei n die Anzahl der Elemente in einem Array ist.
- Zeitkomplexität
*Best-Case-Komplexität = O(1) tritt auf, wenn das Suchelement am ersten Element im Sucharray vorhanden ist.
*Worst-Case-Komplexität = O(n) tritt auf, wenn das Suchelement nicht in der Elementmenge oder im Array vorhanden ist.
*Durchschnittliche Komplexität = O(n) wird bezeichnet, wenn das Element irgendwo im Sucharray vorhanden ist.
Beispiel,
Nehmen wir ein Array von Elementen wie unten angegeben:
45, 78, 12, 67, 08, 51, 39, 26
Um '51' in einem oben angegebenen Array von 8 Elementen zu finden, überprüft ein linearer Suchalgorithmus jedes Element sequentiell, bis sein Zeiger auf 51 im Speicherplatz zeigt. Es dauert O(6) Zeit, um 51 in einem Array zu finden. Um 12 im obigen Array zu finden, dauert es O (3), während es für 26 O (8) Zeit benötigt.
Binäre Suche
Dieser Algorithmus findet bestimmte Elemente, indem er die mittleren Elemente in der Datensammlung vergleicht. Wenn eine Übereinstimmung auftritt, wird der Index des Elements zurückgegeben. Wenn das mittlere Element größer als das Element ist, wird nach einem zentralen Element des linken Teilarrays gesucht. Wenn im Gegensatz dazu das mittlere Element kleiner als das Suchelement ist, wird die Mitte des Elements im rechten Unterarray untersucht. Es fährt mit der Suche nach einem Element fort, bis es es findet oder bis die Größe der Teilarrays null wird.
Die binäre Suche erfordert eine sortierte Reihenfolge der Elemente. Es ist schneller als ein linearer Suchalgorithmus. Es funktioniert nach dem Teile-und-Herrsche-Prinzip.
Laufzeitkomplexität = O(log n)
Der binäre Suchalgorithmus hat die folgenden Komplexitäten:
- Worst-Case-Komplexität = O (n log n)
- Durchschnittliche Komplexität = O (n log n)
- Komplexität im besten Fall = O (1)
Beispiel,
Nehmen wir einen sortierten Algorithmus mit 08 Elementen:
08, 12, 26, 39, 45, 51, 67, 78
Um 51 in einem Array der obigen Elemente zu finden,
Der Algorithmus teilt ein Array in zwei Arrays auf, 08, 12, 26, 39 und 45, 51, 67, 78
Da 51 größer als 39 ist, beginnt es mit der Suche nach Elementen auf der rechten Seite des Arrays.
Es wird weiter in zwei Teile unterteilt, z. B. 45, 51 und 67, 78
Da 51 kleiner als 67 ist, beginnt es mit der Suche links von diesem Unterarray.
Dieses Subarray ist wiederum zweigeteilt als 45 und 51.
Da 51 die Zahl ist, die mit dem Suchelement übereinstimmt, wird die Indexnummer dieses Elements im Array zurückgegeben.
Daraus wird geschlossen, dass sich das Suchelement 51 an der 6. Position in einem Array befindet.
Die binäre Suche reduziert die Zeit auf die Hälfte, da die Anzahl der Vergleiche im Vergleich zum linearen Suchalgorithmus erheblich reduziert wird.
Lesen Sie: Arten von Datenstrukturen in Python
Interpolationssuche
Es ist eine verbesserte Variante des binären Suchalgorithmus und arbeitet an der Sondierungsposition des Suchelements. Ähnlich wie bei binären Suchalgorithmen funktioniert es effizient nur bei der sortierten Datensammlung.
Schlechteste Ausführungszeit = O(n)
Wenn die Position des Zielelements in der Datensammlung bekannt ist, wird eine Interpolationssuche verwendet. Um eine Nummer in dem Telefonverzeichnis zu finden, kann man, wenn man Monicas Telefonnummer suchen möchte, anstatt eine lineare oder binäre Suche zu verwenden, direkt in den Speicherplatz suchen, wo Namen mit 'M' beginnen.
Fazit
Das Suchen in Datenstrukturen bezieht sich auf das Finden eines bestimmten Elements in einem Array von 'n' Elementen. Es gibt zwei Kategorien, nämlich. Sequentielle Suche und Intervallsuche beim Suchen. Fast alle Suchalgorithmen basieren auf einer dieser beiden Kategorien. Lineare und binäre Suche sind die beiden einfachen und leicht zu implementierenden Algorithmen, bei denen binäre schneller arbeiten als lineare Algorithmen.
Obwohl die lineare Suche am unkompliziertesten ist, überprüft sie jedes Element, bis sie eine Übereinstimmung mit dem Suchelement findet, und ist daher effizient, wenn die Datenerfassung nicht korrekt sortiert ist. Wenn die Datensammlung jedoch sortiert ist und die Länge eines Arrays beträchtlich ist, ist die binäre Suche schneller.
Die Datenstruktur ist ein wesentlicher Bestandteil der Computerprogrammierung beim Umgang mit Datensätzen. Programmierer und Entwickler müssen sich ständig mit Grundlagen und Updates in Computerprogrammiertechniken aktualisieren und weiterbilden. Programmierer, die sich mit Datenstrukturen befassen, sollten sich häufig für Kurse entscheiden.
Wenn Sie mehr über Data Science erfahren möchten, besuchen Sie das Executive PG Program in Data Science von IIIT-B & upGrad, das für Berufstätige entwickelt wurde und mehr als 10 Fallstudien und Projekte, praktische Workshops, Mentoring mit Branchenexperten bietet. 1-zu-1 mit Branchenmentoren, über 400 Stunden Lern- und Jobunterstützung bei Top-Unternehmen.
