Unterschied zwischen binärer Suche und lineare Suche

Binäre Suche gegen lineare Suche

Lineare Suche, auch als sequentielle Suche bezeichnet. 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, mit der ein bestimmter Wert in einer sortierten Liste lokalisiert wird. Die Binär -Suchmethode halb.

Was ist lineare Suche?

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

Was ist binäre Suche?

Die binäre Suche ist auch eine Methode, mit der ein bestimmtes Element in einer sortierten Liste lokalisiert werden kann. Diese Methode beginnt mit dem Vergleich des durchsuchten 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 durchsuchte Element größer als das mittlere Element ist, startet es die Methode erneut mit der unteren Hälfte der sortierten Liste. Wenn das durchsuchte Element geringer ist als das mittlere Element, startet es die Methode erneut mit der oberen Hälfte der sortierten Liste. Wenn sich das durchsuchte Element nicht in der Liste befindet, gibt die Methode einen eindeutigen Wert zurück, der dies anzeigt. Daher hindert die binäre Suchmethode die Anzahl der verglichenen Elemente (in jeder Iteration), abhängig vom Ergebnis des Vergleichs. Infolgedessen läuft eine binäre Suche in der logarithmischen Zeit, was zu einer durchschnittlichen Fallleistung von O (log n) führt.

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

Obwohl sowohl lineare Such- als auch binäre Suche Methoden sind, haben sie verschiedene Unterschiede. Während die binäre Suche in sortierten Listen funktioniert, kann die Liner -Suche auch auf ungeortierten Listen funktionieren. Das Sortieren einer Liste hat im Allgemeinen eine durchschnittliche Fallkomplexität von n log n. Die lineare Suche ist einfach und unkompliziert als die binäre Suche. Die lineare Suche ist jedoch zu langsam, um mit großen Listen aufgrund der durchschnittlichen Fallleistung von O (N) verwendet zu werden. Andererseits wird eine binäre Suche als eine effizientere Methode angesehen, die mit großen Listen verwendet werden kann. 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 in nur fünf von zwanzig Büchern gefunden werden kann.