Was ist der Unterschied zwischen linearer Suche und binärer Suche? - Unterschied Zwischen

Was ist der Unterschied zwischen linearer Suche und binärer Suche?

Das Hauptunterschied zwischen linearer Suche und binärer Suche ist das Eine binäre Suche (auch als Halbintervall-Suche oder logarithmische Suche bezeichnet) ist effizienter und benötigt für die Suche eines Elements weniger Zeit als eine lineare Suche (oder eine sequentielle Suche).

Die Suche ist eine Operation, mit der ein Element in einer bestimmten Datenstruktur wie einem Array gesucht werden kann. Es gibt zwei Suchtypen: lineare Suche und binäre Suche. Bei der linearen Suche werden die Elemente eines Arrays nacheinander in sequentieller Reihenfolge geprüft, um festzustellen, ob das erforderliche Element im Array vorhanden ist. Auf der anderen Seite ist die binäre Suche ein effizienterer Algorithmus als die lineare Suche, da der Artikel durch Vergleichen mit dem mittleren Element durchsucht wird.

Wichtige Bereiche

1. Was ist lineare Suche?
- Definition, Funktionalität
2. Was ist die binäre Suche?
- Definition, Funktionalität
3. Was ist der Unterschied zwischen linearer Suche und binärer Suche?
- Vergleich der wichtigsten Unterschiede

Schlüsselbegriffe

Binäre Suche, Lineare Suche, Suchalgorithmus


Was ist lineare Suche?

Die lineare Suche ist ein einfacher Suchalgorithmus. Hier erfolgt die Suche von einem Punkt nach dem anderen. Das ist; Dieser Algorithmus prüft jeden Artikel und sucht nach einem passenden Artikel davon. Wenn das Element nicht vorhanden ist, wird die Suche bis zum Ende der Daten fortgesetzt. Daher ist die lineare Suche ein Algorithmus, mit dem jedes Element in einem Array durchsucht werden kann, um das angegebene Element zu finden.

Bei einer linearen Suche hilft der Zeitverbrauch oder die Anzahl von Vergleichen zum Suchen eines Elements, um die Effizienz des Algorithmus zu bestimmen. Befindet sich das gesuchte Element an der ersten Stelle der Datenstruktur, ist nur ein Vergleich erforderlich. Wenn sich das erforderliche Element an der letzten Position befindet, sind N Vergleiche erforderlich, um das Element zu finden. Hier bezieht sich das N auf die Anzahl der Datenelemente.

Was ist die binäre Suche?

Die binäre Suche ist ein schneller Algorithmus. Es ist jedoch erforderlich, die Datenelemente zu sortieren, bevor eine binäre Suche ausgeführt wird. Es findet das Element durch Vergleichen des am weitesten mittleren Elementes der Sammlung. Daher benötigt die binäre Suche weniger Zeit für die Suche eines bestimmten Elements mit einer geringeren Anzahl von Vergleichen, da das mittlere Element gesucht und das mittlere Element mit dem zu durchsuchenden Element verglichen wird.


Wenn bei einer binären Suche das mittlere Element das erforderliche Element ist, wird dieser Index zurückgegeben. Wenn das mittlere Element höher als das gesuchte Element ist, befindet sich das gesuchte Element im linken Teilfeld des mittleren Elements. Ansonsten befinden sich die Elemente im rechten Unterfeld des mittleren Elements. Dieser Vorgang wird auf dem Unterfeld fortgesetzt, bis die Unterfeldgröße Null wird. Bei diesem Algorithmus verringert sich die Anzahl der zu suchenden Elemente jedes Mal.

Unterschied zwischen linearer Suche und binärer Suche

Definition

Die lineare Suche ist ein Algorithmus zum Suchen eines Elements in einer Liste, indem die Elemente der Liste nacheinander geprüft werden, bis das entsprechende Element gefunden wird. Die binäre Suche ist ein Algorithmus, der die Position eines Zielwerts innerhalb eines sortierten Arrays ermittelt. Dies ist also der Hauptunterschied zwischen linearer Suche und binärer Suche.

Synonyme

Die sequentielle Suche ist ein anderer Begriff für die lineare Suche, während sich die Suche nach einem halben Intervall oder die logarithmische Suche auf dieselbe binäre Suche bezieht.

Zeitliche Komplexität

Die zeitliche Komplexität einer linearen Suche ist O (N), während die zeitliche Komplexität einer binären Suche O (log) ist2N). Dies ist also ein weiterer Unterschied zwischen linearer Suche und binärer Suche.

I'm besten fall

Des Weiteren ist der beste Fall bei einer linearen Suche, das Element an der ersten Position zu finden, während der beste Fall bei der binären Suche das Element an der mittleren Position findet.

Sortieren des Arrays

Bei einer linearen Suche muss das Array vor dem Durchsuchen des Elements nicht sortiert werden. Bei einer binären Suche muss das Array jedoch vor dem Durchsuchen des Elements sortiert werden. Daher macht die Voraussetzung zum Sortieren des Arrays einen Unterschied zwischen linearer Suche und binärer Suche.

Effizienz

Ein weiterer Unterschied zwischen linearer Suche und binärer Suche ist ihre Effizienz. Die binäre Suche ist effizienter als die lineare Suche.

Einfachheit

Außerdem ist die binäre Suche komplexer als die lineare Suche.

Fazit

Lineare Suche und binäre Suche sind zwei Algorithmen, um ein Element in einer Datenstruktur wie einem Array zu suchen. Die binäre Suche ist effizienter und schneller als die lineare Suche, es ist jedoch erforderlich, das Array zuerst zu sortieren, bevor der Suchvorgang ausgeführt wird. Daher besteht der Hauptunterschied zwischen linearer Suche und binärer Suche darin, dass die binäre Suche effizienter ist und im Vergleich zur linearen Suche ein Minimum an Zeit benötigt, um ein Element zu suchen.

Referenz:

1. „Lineare Suche“. Wikipedia, Wikimedia Foundation, 13. Dezember