Der Hauptunterschied zwischen linearer Suche und binärer Suche besteht darin, dass die binäre Suche weniger Zeit in Anspruch nimmt, um ein Element aus der sortierten Liste der Elemente zu durchsuchen. Daraus wird abgeleitet, dass die Effizienz der binären Suchmethode größer ist als die lineare Suche.
Ein weiterer Unterschied besteht darin, dass eine Voraussetzung für die binäre Suche besteht, dh die Elemente müssen sortiert werden, während bei der linearen Suche keine solche Voraussetzung besteht. Beide Suchmethoden verwenden zwar unterschiedliche Techniken, die im Folgenden erläutert werden.
Vergleichstabelle
| Basis zum Vergleich | Lineare Suche | Binäre Suche |
|---|---|---|
| Zeitkomplexität | AUF) | O (log 2 N) |
| Bester Fall Zeit | Erstes Element O (1) | Mittelelement O (1) |
| Voraussetzung für ein Array | Nicht erforderlich | Array muss in sortierter Reihenfolge sein |
| Schlechtester Fall für N Anzahl Elemente | N Vergleiche sind erforderlich | Kann nur nach log 2 N Vergleichen abschließen |
| Kann am implementiert werden | Array und verknüpfte Liste | Kann nicht direkt in der verknüpften Liste implementiert werden |
| Vorgang einfügen | Einfach am Ende der Liste eingefügt | Die Verarbeitung muss an der richtigen Stelle eingefügt werden, um eine sortierte Liste zu verwalten. |
| Algorithmus-Typ | Iterativ in der Natur | Teilen und erobern in der Natur |
| Nützlichkeit | Einfach zu bedienen und keine bestellten Elemente erforderlich. | Trotzdem sollten knifflige Algorithmen und Elemente in der richtigen Reihenfolge angeordnet sein. |
| Zeilen von Code | Weniger | Mehr |
Definition der linearen Suche
Bei einer linearen Suche wird jedes Element eines Arrays einzeln in einer logischen Reihenfolge abgerufen und geprüft, ob es ein gewünschtes Element ist oder nicht. Eine Suche ist nicht erfolgreich, wenn auf alle Elemente zugegriffen wird und das gewünschte Element nicht gefunden wird. Im schlimmsten Fall müssen wir die Anzahl eines Durchschnittsfalls die Hälfte der Größe des Arrays (n / 2) scannen.
Daher kann die lineare Suche als die Technik definiert werden, die das Array sequentiell durchläuft, um das gegebene Element zu lokalisieren. Das unten angegebene Programm veranschaulicht die Suche eines Elements des Arrays mittels Suche.
Effizienz der linearen Suche
Der Zeitverbrauch oder die Anzahl von Vergleichen, die beim Suchen eines Datensatzes in einer Suchtabelle gemacht werden, bestimmen die Effizienz der Technik. Wenn der gewünschte Datensatz an der ersten Position der Suchtabelle vorhanden ist, wird nur ein Vergleich durchgeführt. Wenn der gewünschte Datensatz der letzte ist, müssen n Vergleiche durchgeführt werden. Wenn der Datensatz irgendwo in der Suchtabelle vorhanden sein soll, ist die Anzahl der Vergleiche im Durchschnitt (n + 1/2). Die Worst-Case-Effizienz dieser Technik ist, dass O (n) für die Ausführungsreihenfolge steht.
C Programm zum Suchen eines Elements mit linearer Suchtechnik.
#include #include void main () {int a [100], n, i, item, loc = -1; clrscr (); printf ("\ nGeben Sie die Anzahl der Elemente ein:"); scanf ("% d", & n); printf ("Geben Sie die Zahlen ein: \ n"); für (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("\ nGeben Sie die zu durchsuchende Nummer ein:"); scanf ("% d", & item); für (i = 0; i = 0) {printf ("\ n% d befindet sich in Position% d:", item, loc + 1); } else {printf ("\ n Artikel existiert nicht"); } getch (); } Definition der binären Suche
Die binäre Suche ist ein äußerst effizienter Algorithmus. Diese Suchmethode benötigt weniger Zeit, um den angegebenen Artikel in möglichst geringen Vergleichen zu durchsuchen. Um die binäre Suche durchzuführen, müssen wir zuerst die Array-Elemente sortieren.
Die Logik hinter dieser Technik ist unten angegeben:
- Suchen Sie zuerst das mittlere Element des Arrays.
- Das mittlere Element des Arrays wird mit dem zu durchsuchenden Element verglichen.
Es können drei Fälle auftreten:
- Wenn das Element das erforderliche Element ist, ist die Suche erfolgreich.
- Wenn das Element weniger als das gewünschte Element ist, suchen Sie nur die erste Hälfte des Arrays.
- Wenn es größer als das gewünschte Element ist, suchen Sie in der zweiten Hälfte des Arrays.
Wiederholen Sie dieselben Schritte, bis ein Element im Suchbereich gefunden wird oder erschöpft ist. Bei diesem Algorithmus wird jedes Mal, wenn der Suchbereich reduziert wird. Daher ist die Anzahl der Vergleiche höchstens log (N + 1). Im Vergleich zur linearen Suche ist dies daher ein effizienter Algorithmus. Das Array muss jedoch vor der binären Suche sortiert werden.
C Programm zum Suchen eines Elements mit binärer Suchtechnik.
#include void main () {int i, anfangen, ende, mitte, n, suchen, array [100]; printf ("Anzahl der Elemente eingeben \ n"); scanf ("% d", & n); printf ("Geben Sie die% d-Nummern ein \ n", n); für (i = 0; i <n; i ++) scanf ("% d", & Array [i]); printf ("Geben Sie die zu suchende Nummer ein \ n"); scanf ("% d", & Suche); beg = 0; end = n - 1; Mitte = (Beg + Ende) / 2; while (Beg <= Ende) {if (Array [Mitte] Ende) printf ("Suche ist nicht erfolgreich!% d ist nicht in der Liste enthalten. \ n", Suche); getch (); } Hauptunterschiede zwischen linearer Suche und binärer Suche
- Die lineare Suche ist iterativ und verwendet einen sequentiellen Ansatz. Auf der anderen Seite implementiert die binäre Suche den Divide and Conquer-Ansatz.
- Die zeitliche Komplexität der linearen Suche ist O (N), während die binäre Suche O (log 2 N) hat.
- Die beste Zeit bei der linearen Suche ist für das erste Element, dh O (1). Im Gegensatz dazu ist es bei der binären Suche für das mittlere Element, dh O (1).
- Bei der linearen Suche ist der ungünstigste Fall zum Suchen eines Elements N Vergleichszahlen. Im Gegensatz dazu ist es eine log 2 N Vergleichsnummer für die binäre Suche.
- Die lineare Suche kann sowohl in einem Array als auch in einer verknüpften Liste implementiert werden, während die binäre Suche nicht direkt in einer verknüpften Liste implementiert werden kann.
- Wie wir wissen, erfordert die binäre Suche das sortierte Array. Dies ist der Grund. Sie müssen an der richtigen Stelle eingefügt werden, um eine sortierte Liste zu verwalten. Im Gegensatz dazu erfordert die lineare Suche keine sortierten Elemente, sodass Elemente leicht am Ende der Liste eingefügt werden können.
- Die lineare Suche ist einfach zu bedienen und es sind keine geordneten Elemente erforderlich. Auf der anderen Seite ist der binäre Suchalgorithmus jedoch schwierig und die Elemente müssen notwendigerweise in der Reihenfolge angeordnet sein.
Fazit
Sowohl lineare als auch binäre Suchalgorithmen können je nach Anwendung nützlich sein. Wenn ein Array die Datenstruktur ist und die Elemente in sortierter Reihenfolge angeordnet sind, wird für die schnelle Suche die binäre Suche bevorzugt. Wenn die verknüpfte Liste die Datenstruktur ist, unabhängig von der Anordnung der Elemente, wird die lineare Suche übernommen, da keine direkte Implementierung des binären Suchalgorithmus möglich ist.
Der typische binäre Suchalgorithmus kann nicht für verknüpfte Listen verwendet werden, da die verknüpfte Liste dynamischer Natur ist und nicht bekannt ist, wo das mittlere Element tatsächlich zugewiesen ist. Daher ist es erforderlich, die Variation des binären Suchalgorithmus zu entwerfen, die auch auf verknüpfte Liste angewendet werden kann, da die binäre Suche schneller ausgeführt wird als eine lineare Suche.
