Inhalt

• Vergleichstabelle
• Definition der linearen Suche
• Definition der binären Suche
• Fazit

Lineare Suche und binäre Suche sind die beiden Methoden, die in Arrays für verwendet werden suche die Elemente. Beim Suchen wird ein Element in der Liste der Elemente gefunden, die in einer beliebigen Reihenfolge oder zufällig gespeichert sind.

Der Hauptunterschied zwischen der linearen Suche und der binären Suche besteht darin, dass die Suche nach einem Element aus der sortierten Liste von Elementen weniger Zeit in Anspruch nimmt. Daraus wird geschlossen, dass die Effizienz der binären Suchmethode größer ist als die der linearen Suche.

Ein weiterer Unterschied zwischen den beiden besteht darin, dass eine Voraussetzung für die binäre Suche besteht, d. H., Dass die Elemente vorhanden sein müssen sortiert während der linearen Suche gibt es keine solche Voraussetzung. Obwohl beide Suchmethoden unterschiedliche Techniken verwenden, die unten diskutiert werden.

1. Vergleichstabelle
2. Definition
3. Hauptunterschiede
4. Fazit

Vergleichstabelle

Vergleichsbasis	Lineare Suche	Binäre Suche
Zeitliche Komplexität	AUF)	O (log 2 N)
Beste Fallzeit	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 Elemente	N Vergleiche sind erforderlich	Kann erst nach loggen schließen2N Vergleiche
Kann am implementiert werden	Array und verknüpfte Liste	Kann nicht direkt in verknüpfte Listen implementiert werden
Operation einfügen	Einfach am Ende der Liste einfügen	Verarbeitung erforderlich, um eine sortierte Liste an der richtigen Stelle einzufügen.
Algorithmus-Typ	Iterativ in der Natur	Teilen und erobern Sie die Natur
Nützlichkeit	Einfach zu bedienen und keine bestellten Elemente erforderlich.	Trotzdem sollten knifflige Algorithmen und Elemente in der richtigen Reihenfolge angeordnet werden.
Zeilen von Code	Weniger	Mehr

Definition der linearen Suche

Bei einer linearen Suche wird jedes Element eines Arrays nacheinander in einer logischen Reihenfolge abgerufen und überprüft, ob es sich um ein gewünschtes Element handelt oder nicht. Eine Suche schlägt fehl, wenn auf alle Elemente zugegriffen wird und das gewünschte Element nicht gefunden wird. Im schlimmsten Fall muss die Zahl eines durchschnittlichen Falls möglicherweise die Hälfte der Größe des Arrays (n / 2) abgetastet werden.

Daher kann die lineare Suche als die Technik definiert werden, die das Array sequentiell durchläuft, um das gegebene Objekt zu lokalisieren. Das folgende Programm veranschaulicht die Suche nach einem Element des Arrays mit search.

Effizienz der linearen Suche

Der Zeitaufwand oder die Anzahl der Vergleiche, die beim Durchsuchen eines Datensatzes in einer Suchtabelle durchgeführt werden, bestimmen die Effizienz der Technik. Befindet sich der gewünschte Datensatz an der ersten Position der Suchtabelle, wird nur ein Vergleich durchgeführt. Wenn der gewünschte Datensatz der letzte ist, müssen n Vergleiche durchgeführt werden. Wenn der Datensatz in der Suchtabelle enthalten sein soll, beträgt die Anzahl der Vergleiche im Durchschnitt (n + 1/2). Der schlechteste Wirkungsgrad dieser Technik ist O (n) steht für die Ausführungsreihenfolge.

C Programm um ein Element mit linearer Suchtechnik zu suchen.

#umfassen #umfassen void main () {int a, n, i, item, loc = -1; clrscr (); f (" nGeben Sie die Anzahl der Elemente ein:"); scanf ("% d", & n); f ("Geben Sie die Zahlen ein: n"); für (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" nGeben Sie die zu durchsuchende Nummer ein:"); scanf ("% d", & item); für (i = 0; i <= n-1; i ++) {if (item == a) {loc = i; brechen; }} if (loc> = 0) {f (" n% d befindet sich an Position% d:", item, loc + 1); } else {f (" n Element existiert nicht"); } getch (); }

Definition der binären Suche

Die binäre Suche ist ein äußerst effizienter Algorithmus. Diese Suchtechnik nimmt weniger Zeit in Anspruch, um das gegebene Objekt 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:

1. Wenn das Element das erforderliche Element ist, ist die Suche erfolgreich.
2. Wenn das Element kleiner als das gewünschte Element ist, durchsuchen Sie nur die erste Hälfte des Arrays.
3. 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 wurde oder erschöpft ist. Bei diesem Algorithmus wird der Suchbereich jedes Mal kleiner. Daher beträgt die Anzahl der Vergleiche höchstens log (N + 1). Daher ist es im Vergleich zur linearen Suche ein effizienter Algorithmus, aber das Array muss vor der binären Suche sortiert werden.

C Programm um ein Element mit binärer Suchtechnik zu finden.

#umfassen void main () {int i, beg, end, middle, n, search, array; f ("Geben Sie die Anzahl der Elemente ein n"); scanf ("% d", & n); f ("% d Zahlen eingeben n", n); für (i = 0; i <n; i ++) scanf ("% d", & array); f ("Zu suchende Nummer eingeben n"); scanf ("% d", & search); betteln = 0; Ende = n - 1; Mitte = (Beginn + Ende) / 2; while (beg <= end) {if (array <search) beg = middle + 1; sonst if (array == search) {f ("Suche erfolgreich. n% d an Position% d gefunden. n", Suche, Mitte + 1); brechen; } else end = middle - 1; Mitte = (Beginn + Ende) / 2; } if (beg> end) f ("Die Suche ist fehlgeschlagen!% d ist nicht in der Liste vorhanden. n", search); getch (); }

1. Die lineare Suche ist iterativ und verwendet einen sequentiellen Ansatz. Auf der anderen Seite implementiert die binäre Suche den Divide- und Conquer-Ansatz.
2. Die zeitliche Komplexität der linearen Suche beträgt O (N), während die binäre Suche O (log₂N).
3. Die beste Fallzeit bei der linearen Suche ist für das erste Element, d. H. O (1). Bei der binären Suche hingegen gilt dies für das mittlere Element, d. H. O (1).
4. Bei der linearen Suche ist der schlechteste Fall für die Suche nach einem Element die Anzahl N des Vergleichs. Im Gegensatz dazu ist es log₂N Vergleichsnummer für binäre Suche.
5. Die lineare Suche kann sowohl in einem Array als auch in einer verknüpften Liste implementiert werden, wohingegen die binäre Suche nicht direkt in einer verknüpften Liste implementiert werden kann.
6. Wie wir wissen, erfordert die binäre Suche das sortierte Array, das der Grund ist. Es muss verarbeitet werden, um eine sortierte Liste an der richtigen Stelle einzufügen. Im Gegensatz dazu erfordert die lineare Suche keine sortierten Elemente, sodass Elemente einfach am Ende der Liste eingefügt werden können.
7. Die lineare Suche ist einfach zu bedienen und es werden keine geordneten Elemente benötigt. Andererseits ist der binäre Suchalgorithmus jedoch schwierig und die Elemente müssen in der richtigen Reihenfolge angeordnet sein.

Fazit

Je nach Anwendung können sowohl lineare als auch binäre Suchalgorithmen nützlich sein. Wenn ein Array die Datenstruktur ist und die Elemente in sortierter Reihenfolge angeordnet sind, wird die binäre Suche bevorzugt schnellsuche. Wenn die verknüpfte Liste die Datenstruktur ist, unabhängig davon, wie die Elemente angeordnet sind, wird die lineare Suche übernommen, da der Algorithmus für die binäre Suche nicht direkt implementiert werden kann.

Der typische binäre Suchalgorithmus kann nicht auf verknüpfte Listen angewendet werden, da verknüpfte Listen dynamischer Natur sind 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 für verknüpfte Listen verwendet werden kann, da die binäre Suche schneller ausgeführt wird als eine lineare Suche.