Binäre Suche vs. lineare Suche
Lineare Suche, auch als sequentielle Suche bekannt, ist der einfachste Suchalgorithmus. Es sucht nach einem bestimmten Wert in einer Liste, indem es jedes Element in der Liste überprüft. Die binäre Suche ist auch eine Methode, die verwendet wird, um einen bestimmten Wert in einer sortierten Liste zu finden. Die binäre Suchmethode halbiert die Anzahl der geprüften Elemente (in jeder Iteration) und verkürzt so die Zeit, die benötigt wird, um das angegebene Element in der Liste zu finden.
Was ist die lineare Suche?
Die lineare Suche ist die einfachste Suchmethode, bei der jedes Element in einer Liste der Reihe nach geprü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 zu durchsuchende Element. Die Ausgabe ist wahr, wenn sich das angegebene Element in der bereitgestellten Sequenz befindet, oder falsch, wenn es sich nicht in der Sequenz befindet. Da diese Methode jedes Element in der Liste prüft, bis das angegebene Element gefunden wird, durchläuft sie im schlimmsten Fall alle Elemente in der Liste, bevor sie das erforderliche Element findet. 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. Aber das ist sehr einfach und einfacher umzusetzen.
Was ist die binäre Suche?
Binäre Suche ist auch eine Methode, die verwendet wird, 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 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, startet es das Verfahren erneut, wobei nur die untere Hälfte der sortierten Liste verwendet wird. Wenn das gesuchte Element kleiner als das mittlere Element ist, startet es das Verfahren erneut, 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 anzeigt. Daher halbiert das binäre Suchverfahren die Anzahl der verglichenen Elemente (in jeder Iteration), abhängig vom Ergebnis des Vergleichs. Folglich läuft die binäre Suche in logarithmischer Zeit, was zu einer durchschnittlichen Fallleistung von o(log n) führt.
Was ist der Unterschied zwischen der binären Suche und der linearen Suche?
Obwohl sowohl die lineare Suche als auch die binäre Suche Suchmethoden sind, weisen sie einige Unterschiede auf. Während die binäre Suche mit sortierten Listen arbeitet, kann die lineare Suche auch mit unsortierten Listen arbeiten. Das Sortieren einer Liste hat im Allgemeinen eine durchschnittliche Fallkomplexität von n log n. Die lineare Suche ist einfacher und unkomplizierter 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 gilt die binäre Suche als effizienteres Verfahren, das bei großen Listen verwendet werden könnte. Die Implementierung der binären Suche könnte jedoch ziemlich 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 zu finden ist.
