Contents
Was ist lineare Suche?
Die lineare Suche, auch sequentielle Suche genannt, ist der einfachste Suchalgorithmus, der nach einem Element in einer Liste in sequentieller Reihenfolge sucht. Es beruht auf der Technik, eine Liste von Anfang bis Ende zu durchlaufen, indem die Eigenschaften aller Elemente untersucht werden, die auf dem Weg gefunden werden. Lineares Sear ist meist sehr einfach zu implementieren und praktisch, wenn die Liste nur wenige Elemente enthält oder wenn Sie eine einzelne Suche in einer ungeordneten Liste durchführen (Liste, in der die Elemente nicht sortiert sind).
Die lineare Suche wird mit den folgenden Schritten implementiert:
Schritt 1- Lesen Sie das Suchelement vom Benutzer
Schritt 2- Vergleichen Sie das Suchelement mit dem ersten Element in der Liste.
Schritt 3- Wenn beide übereinstimmen, dann zeige ”vorgegebenes Element gefunden” an und beende die Funktion.
Schritt 4 – Wenn beide nicht übereinstimmen, vergleichen Sie das Suchelement mit dem nächsten Element in der Liste.
Schritt 5- Wiederholen Sie die Schritte 3 und 4, bis das Suchelement mit dem letzten Element in der Liste verglichen wird.
Schritt 6- Wenn das letzte Element in der Liste ebenfalls nicht übereinstimmt, dann zeigen Sie ”Element wurde nicht gefunden” an und beenden Sie die Funktion.
Was Sie über die lineare Suche wissen müssen
- Die lineare Suche ist ein Algorithmus, um ein Element in einer Liste zu finden, indem die Elemente der Liste sequentiell überprüft werden, bis das passende Element gefunden wird.
- Eine lineare Suche scannt ein Element nach dem anderen, ohne zu einem Element zu springen.
- Lineare Suchen können in jedem linearen Container (Vektor, Single Linked List, Double Linked List) implementiert werden.
- Die lineare Suche ist einfach zu verwenden, da keine geordneten Elemente erforderlich sind.
- Die lineare Suche in der Programmiersprache C erfordert keine sortierten Elemente, daher werden die Elemente bequem am Ende der Liste eingefügt.
- Die lineare Suche ist repetitiv oder iterativ und verwendet in ihrer Funktionalität den sequentiellen Ansatz.
- Bei der linearen Suche erfolgt die Leistung durch Gleichheitsvergleiche.
- Bei der linearen Suche entspricht das Worst-Case-Szenario zum Durchsuchen eines Elements der Zahl O(n) des Vergleichs. Es tritt auf, wenn der Suchschlüssel das letzte Element ist.
- Das beste Szenario bei einer linearen Suche besteht darin, das Element an der ersten Position O(1) zu finden. Es tritt auf, wenn der Suchschlüssel das erste Element ist.
- Die Zeitkomplexität der linearen Suche ist zufällig O(n). Dabei ist n die Anzahl der Elemente im Eingabebereich.
Was ist binäre Suche?
Die binäre Suche ist ein effizienter Algorithmus zum Auffinden eines Elements aus einer sortierten Liste von Elementen. Es funktioniert, indem es den Teil der Liste, der das Element enthalten könnte, wiederholt in zwei Hälften teilt, bis Sie die möglichen Positionen auf nur einen eingegrenzt haben. Eine der gebräuchlichsten Möglichkeiten, die binäre Suche zu verwenden, besteht darin, ein Element in einem sortierten Array oder einer großen Liste zu finden. Seine Zeitkomplexität macht es im Vergleich zu anderen Sortieralgorithmen sehr schnell.
Der binäre Suchalgorithmus arbeitet nach dem Prinzip des Teilens und Herrschens. Eine der Haupteinschränkungen der binären Suche besteht darin, dass das Array oder die Liste von Elementen sortiert werden muss, damit der Algorithmus daran arbeiten kann.
Die binäre Suche sucht nach einem bestimmten Element, indem sie das mittlere Element der Sammlung vergleicht. Wenn eine Übereinstimmung auftritt, wird der Index des Elements zurückgegeben. Wenn das mittlere Element größer als das Element ist, wird das Element im Unterarray links vom mittleren Element gesucht. Andernfalls wird das Element im Unterarray rechts neben dem mittleren Element gesucht. Dieser Vorgang wird auch auf dem Unterarray fortgesetzt, bis die Größe des Unterarrays auf Null reduziert wird.
Was Sie über die lineare Suche wissen müssen
- Die binäre Suche ist ein Algorithmus, der die Position eines Zielwerts innerhalb eines sortierten Arrays findet.
- Eine binäre Suche verkürzt die Suche auf die Hälfte, sobald die Mitte einer sortierten Liste gefunden wird.
- Binäre Suchen können nur in Datenstrukturen implementiert werden, bei denen eine Zweiwege-Traversierung möglich ist. Es ist schwierig, direkt eine binäre Suche in einer einzelnen verknüpften Liste zu implementieren, da wir nicht in beide Richtungen durchqueren können.
- Die binäre Suche ist etwas kompliziert, da Elemente notwendigerweise in einer bestimmten Reihenfolge angeordnet sind.
- Eine binäre Suche in der Programmiersprache C erfordert sortierte Arrays für eine effektive Leistung. Dies erleichtert das Einfügen von Elementen an der gewünschten Stelle und im Wesentlichen die Pflege sortierter Listen.
- Die binäre Suche verwendet in ihrer Funktionalität den Divide-and-Conquer-Ansatz. Es teilt das Sortiment in zwei Teile; links und rechts und findet immer wieder rekursiv.
- Bei der binären Suche erfolgt die Leistung durch das Anordnen von Vergleichen.
- Bei der binären Suche ist das Worst-Case-Szenario eine Anzahl von O(Log 2 n) Ähnlichkeiten.
- Das beste Szenario besteht darin, das Element in der mittleren Position O(1) zu finden. Es tritt auf, wenn sich der Suchschlüssel in der Mitte der sortierten Liste befindet.
- Die Zeitkomplexität der binären Suche beträgt O(log 2 n). Dabei ist n die Anzahl der Elemente im Eingabebereich.
Lesen Sie auch: Unterschied zwischen binärem Baum und binärem Suchbaum
Unterschied zwischen linearer Suche und binärer Suche in Tabellenform
| VERGLEICHSGRUNDLAGE | LINEARE SUCHE | BINÄRE SUCHE |
| Beschreibung | Die lineare Suche ist ein Algorithmus, um ein Element in einer Liste zu finden, indem die Elemente der Liste sequentiell überprüft werden, bis das passende Element gefunden wird. | Die binäre Suche ist ein Algorithmus, der die Position eines Zielwerts innerhalb eines sortierten Arrays findet. |
| Wie es funktioniert | Eine lineare Suche scannt ein Element nach dem anderen, ohne zu einem Element zu springen. | Eine binäre Suche verkürzt die Suche auf die Hälfte, sobald die Mitte einer sortierten Liste gefunden wird. |
| Implementierung | Lineare Suchen können in jedem linearen Container (Vektor, Single Linked List, Double Linked List) implementiert werden. | Binäre Suchen können nur in Datenstrukturen implementiert werden, bei denen eine Zweiwege-Traversierung möglich ist. |
| Komplexität | Die lineare Suche ist einfach zu verwenden, da keine geordneten Elemente erforderlich sind. | Die binäre Suche ist etwas kompliziert, da Elemente notwendigerweise in einer bestimmten Reihenfolge angeordnet sind. |
| Sortierte Elemente | Die lineare Suche in der Programmiersprache C erfordert keine sortierten Elemente, daher werden die Elemente bequem am Ende der Liste eingefügt. | Eine binäre Suche in der Programmiersprache C erfordert sortierte Arrays für eine effektive Leistung. Dies erleichtert das Einfügen von Elementen an der gewünschten Stelle und im Wesentlichen die Pflege sortierter Listen. |
| Sich nähern | Die lineare Suche ist repetitiv oder iterativ und verwendet in ihrer Funktionalität den sequentiellen Ansatz. | Die binäre Suche verwendet in ihrer Funktionalität den Divide-and-Conquer-Ansatz. |
| Leistung | Bei der linearen Suche erfolgt die Leistung durch Gleichheitsvergleiche. | Bei der binären Suche erfolgt die Leistung durch das Anordnen von Vergleichen. |
| Worst-Case-Szenario | Bei der linearen Suche entspricht das Worst-Case-Szenario zum Durchsuchen eines Elements der Zahl O(n) des Vergleichs. | Bei der binären Suche ist das Worst-Case-Szenario eine Anzahl von O(Log 2 n) Ähnlichkeiten. |
| Best-Case-Szenario | Das beste Szenario bei einer linearen Suche besteht darin, das Element an der ersten Position O(1) zu finden. | Das beste Szenario besteht darin, das Element in der mittleren Position O(1) zu finden. |
| Zeitkomplexität | Die Zeitkomplexität der linearen Suche ist zufällig O(n). | Die Zeitkomplexität der binären Suche beträgt O(log 2 n). |