Binäre Suche vs Lineare Suche
Die lineare Suche, auch als sequentielle Suche bezeichnet, ist der einfachste Suchalgorithmus. Es sucht nach einem bestimmten Wert in einer Liste, indem jedes Element in der Liste überprüft wird. Die binäre Suche ist auch eine Methode, um einen bestimmten Wert in einer sortierten Liste zu finden. Die binäre Suchmethode halbiert die Anzahl der überprüften Elemente (in jeder Iteration) und reduziert die Zeit, die zum Auffinden des angegebenen Elements in der Liste benötigt wird.
Was ist lineare Suche?
Die lineare Suche ist die einfachste Suchmethode, bei der jedes Element in einer Liste nacheinander überprüft wird, bis ein bestimmtes Element gefunden wird. Die Eingabe für die lineare Suchmethode ist eine Sequenz (z. B. ein Array, eine Sammlung 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 beträgt 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 leichter zu implementieren.
Was ist binäre Suche?
Die binäre Suche ist auch eine Methode, um ein bestimmtes Element in einer sortierten Liste zu finden. Diese Methode vergleicht zunächst das gesuchte Element mit den Elementen in der Mitte der Liste. Wenn der Vergleich ergibt, 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 erneut gestartet, wobei nur die untere Hälfte der sortierten Liste verwendet wird. Wenn das gesuchte Element kleiner als das mittlere Element ist, wird die Methode erneut gestartet, wobei nur die obere Hälfte der sortierten Liste verwendet wird. 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,Die binäre Suche wird in logarithmischer Zeit ausgeführt, 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 als auch die binäre Suche Suchmethoden sind, weisen sie mehrere Unterschiede auf. Während die binäre Suche sortierte Listen bearbeitet, kann die Linersuche auch unsortierte Listen bearbeiten. Das Sortieren einer Liste hat im Allgemeinen eine durchschnittliche Fallkomplexität von n log n. Die lineare Suche ist einfach und unkompliziert zu implementieren als die binäre Suche. Die lineare Suche ist jedoch aufgrund ihrer o (n) durchschnittlichen Fallleistung zu langsam, um mit großen Listen verwendet zu werden. Andererseits wird die binäre Suche als effizientere Methode angesehen, die bei großen Listen verwendet werden kann. Die Implementierung der binären Suche könnte jedoch recht schwierig 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.
