Unterschied zwischen binärer Suche und linearer Suche

Binäre Suche gegen lineare Suche

Die lineare Suche, auch als sequenzielle Suche bezeichnet, ist der einfachste Suchalgorithmus. Es sucht nach einem angegebenen Wert in einer Liste, indem es jedes Element in der Liste überprüft. Die binäre Suche ist auch eine Methode, um einen angegebenen Wert in einer sortierten Liste zu finden. Die binäre Suchmethode halbiert die Anzahl der überprüften Elemente (in jeder Iteration), wodurch die Zeit zum Suchen des angegebenen Elements in der Liste reduziert wird.

Was ist lineare Suche??

Die lineare Suche ist die einfachste Suchmethode, bei der jedes Element in einer Liste nacheinander geprüft wird, bis ein bestimmtes Element gefunden wird. Die Eingabe für die lineare Suchmethode ist eine Sequenz (z. B. ein Array, eine Auflistung oder eine Zeichenfolge) und das Element, das durchsucht werden muss. Die Ausgabe ist true, wenn sich das angegebene Element innerhalb der angegebenen Sequenz befindet, oder false, wenn es sich nicht in der Sequenz befindet. Da diese Methode jedes Element in der Liste überprüft, bis das angegebene Element gefunden wurde, werden im schlimmsten Fall alle Elemente in der Liste durchlaufen, bevor das erforderliche Element gefunden wird. Die Komplexität der linearen Suche ist o (n). Daher wird es als zu langsam angesehen, um bei der Suche nach Elementen in großen Listen verwendet zu werden. Dies ist jedoch sehr einfach und einfacher umzusetzen.

Was ist die binäre Suche??

Die binäre Suche ist auch eine Methode, um ein bestimmtes Element in einer sortierten Liste zu finden. Diese Methode beginnt mit dem Vergleich des gesuchten Elements mit den Elementen in der Mitte der Liste. Wenn der Vergleich feststellt, dass die beiden Elemente gleich sind, stoppt die Methode und gibt die Position des Elements zurück. Wenn das gesuchte Element größer als das mittlere Element ist, wird die Methode nur mit der unteren Hälfte der sortierten Liste erneut gestartet. Wenn das gesuchte Element kleiner als das mittlere Element ist, wird die Methode nur mit der oberen Hälfte der sortierten Liste erneut gestartet. Wenn sich das gesuchte Element nicht in der Liste befindet, gibt die Methode einen eindeutigen Wert zurück, der dies angibt. Daher halbiert die binäre Suchmethode die Anzahl der verglichenen Elemente (in jeder Iteration) abhängig vom Ergebnis des Vergleichs. Folglich läuft die binäre Suche in logarithmischer Zeit ab, was zu einer durchschnittlichen Fallleistung von o (log n) führt.

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

Obwohl sowohl die lineare Suche als auch die binäre Suche Suchmethoden sind, gibt es mehrere Unterschiede. Während die binäre Suche für sortierte Listen ausgeführt wird, kann die Linersuche auch für unsortierte Listen ausgeführt werden. Das Sortieren einer Liste hat im Allgemeinen eine durchschnittliche Fallkomplexität von n log n. Die lineare Suche ist einfacher und unkomplizierter als die binäre Suche. Die lineare Suche ist jedoch aufgrund ihrer durchschnittlichen Fallleistung (n) zu langsam, um sie mit großen Listen zu verwenden. Auf der anderen Seite wird die binäre Suche als eine effizientere Methode betrachtet, die mit großen Listen verwendet werden kann. Die Implementierung der binären Suche könnte jedoch recht kompliziert sein, und eine Studie hat gezeigt, dass der genaue Code für die binäre Suche nur in fünf von zwanzig Büchern gefunden werden kann.