Warum wird die binäre Suche, die sortierte Daten benötigt, als besser angesehen als die lineare Suche?

Ich habe immer gehört, dass die lineare Suche ein naiver Ansatz ist und die binäre Suche aufgrund der besseren asymptotischen Komplexität leistungsfähiger ist als sie. Aber ich habe nie verstanden, warum es besser ist als eine lineare Suche, wenn vor einer binären Suche eine Sortierung erforderlich ist.

Die lineare Suche ist O(n)und die binäre Suche ist O(log n). Das scheint die Grundlage dafür zu sein, dass die binäre Suche besser ist. Die binäre Suche erfordert jedoch eine Sortierung O(n log n)nach den besten Algorithmen. Die binäre Suche sollte also eigentlich nicht schneller sein, da sie eine Sortierung erfordert.

Ich lese CLRS, in dem der Autor impliziert, dass es bei der Einfügesortierung besser ist, die Binärsuche zu verwenden, um die Stelle zu finden, an der das Element eingefügt werden muss, anstatt den naiven linearen Suchansatz zu verwenden. In diesem Fall scheint dies gerechtfertigt zu sein, da bei jeder Schleifeniteration eine sortierte Liste vorhanden ist, über die die binäre Suche angewendet werden kann. Aber im allgemeinen Fall, in dem es keine Garantie für den zu durchsuchenden Datensatz gibt, ist die binäre Suche aufgrund von Sortieranforderungen nicht tatsächlich schlechter als die lineare Suche?

Gibt es irgendwelche praktischen Überlegungen, die ich übersehen habe und die die binäre Suche besser machen als die lineare Suche? Oder wird die binäre Suche als besser angesehen als die lineare Suche, ohne die für die Sortierung erforderliche Rechenzeit zu berücksichtigen?

Gibt es irgendwelche praktischen Überlegungen, die ich übersehen habe, um die binäre Suche besser als die lineare Suche zu machen?

Ja - Sie müssen die O (n log n) -Sortierung nur einmal durchführen und können dann die O (log n) -Binärsuche so oft durchführen, wie Sie möchten, während die lineare Suche jedes Mal O (n) ist.

Dies ist natürlich nur dann von Vorteil, wenn Sie tatsächlich mehrere Suchvorgänge mit denselben Daten durchführen. Aber "einmal schreiben, oft lesen" -Szenarien sind weit verbreitet.

Die Grundannahme ist, dass Sie keine einzige Suche durchführen.

Wenn Sie also dieselben Daten mehrmals durchsuchen müssen, müssen Sie nur einmal sortieren und können von der binären Suche profitieren.

Wenn Sie häufig suchen und Daten ändern, empfiehlt es sich, eine sortierte Liste zu verwenden, in der neue Einträge in der Liste sortiert werden.

Daher ist die binäre Suche besser, wenn Sie dieselbe Liste mehrmals durchsuchen, ohne erneut suchen zu müssen.

Wenn Sie jedes Mal sortieren müssen, bevor Sie suchen, gibt es keinen Vorteil.

Bitte beachten Sie, dass es Sortieralgorithmen gibt, die sehr schnell sind, wenn die Liste bereits sortiert (oder fast sortiert) ist. Die meisten Leistungsbestimmungen erwarten eine unsortierte Liste.

Denn sobald Sie eine sortierte Liste haben, müssen Sie sie nicht jedes Mal neu sortieren. Wenn Sie also mehr als O (log n) Suchanfragen im Voraus sortieren, erhalten Sie einen Gewinn ( O(n log n + k log n)vsO(k*n)

Stellen Sie sich zwei Telefonbücher vor.

Ein Telefonbuch enthält die Namen in alphabetischer Reihenfolge. Um den gewünschten Eintrag zu finden, öffnen Sie ihn in der Mitte, überprüfen ihn und bewegen sich dann vorwärts oder rückwärts, je nachdem, ob Sie über- oder unterschritten haben.

Das andere Telefonbuch enthält die Namen in zufälliger Reihenfolge. Um den gewünschten Eintrag zu finden, beginnen Sie am Anfang und fahren fort, bis Sie das Gewünschte gefunden haben.

Funktioniert das zweite Buch in einer Stadt mit angemessener Größe?

Ich denke, dass der Wert der binären Suche über die lineare Suche kontextabhängig ist. Wenn Sie mit einem enormen ungeordneten Datensatz beginnen und nur eine kleine Anzahl von Elementen davon zupfen möchten, ist das Sortieren und Durchführen einer binären Suche langsam. Wenn Sie jedoch während der gesamten Lebensdauer Ihrer Anwendung eine geordnete Liste führen und regelmäßig darauf zugreifen, ist die binäre Suche ein weitaus besserer Weg.

Wie viele andere geantwortet haben, ist die binäre Suche in der Tat vorzuziehen, da der Sortierschritt nur einmal durchgeführt werden kann und die eigentliche Suche dann so oft durchgeführt werden kann, wie Sie möchten. Für bestimmte Werte von n (dh bestimmte Eingabegrößen) ist die binäre Suche jedoch immer leistungsfähiger als die lineare Suche (selbst für einen einzelnen Lauf).

Der "Wendepunkt" wird durch Lösen der asymptotischen Komplexitätsgleichung berechnet:

n log n + log n = n

Wie Sie auf Wolfram Alpha sehen können, gibt es einen numerischen Wert für n , der sicherstellt, dass die binäre Suche und Sortierung immer schneller ist als die lineare Suche allein. Natürlich hängt der tatsächliche Wert von n , der in Ihrem Fall funktioniert, von vielen Faktoren ab, die möglicherweise schwer abzuschätzen sind.

Nach diesem interessanten Artikel von Mark Probst, der einige ausführliche Performance-Messungen auf aktuellen Prozessoren enthält:

Wenn Sie ein sortiertes Array von Ganzzahlen durchsuchen müssen und die Leistung wirklich sehr wichtig ist, verwenden Sie die lineare Suche, wenn Ihr Array eine Größe von weniger als 64 Elementen hat, und die binäre Suche, wenn es darüber liegt.

Mit den Worten des Laien:

Wenn Sie eine ungeordnete Liste mit zehn Milliarden Artikeln haben und der Artikel, nach dem Sie suchen, der letzte ist, werden Sie am Ende die zehn Milliarden Artikel lesen.

Bei der binären Suche kann die Indizierung nur einmal durchgeführt werden. Spätere Einfügungen können an der richtigen Stelle vorgenommen werden, um die Reihenfolge aufrechtzuerhalten.

Zwar wurden bereits viele gute Gründe für "Binäre Suche ist besser" aufgeführt, wir können jedoch auch einen Blick auf die Vorteile aus Benutzersicht werfen:

Während Sie normalerweise sehr gut mit der geringen Wartezeit leben können, die zwischen Dateneingabeaktionen aufgeteilt ist, wenn Sie eine sortierte Einfügung durchführen, möchten Sie, dass die "Suche" so schnell wie möglich erfolgt. Aus Sicht des Benutzers bietet sortiertes Einfügen in Kombination mit einer binären Suche die bestmögliche Benutzererfahrung.