Binäre Suche

Question

Ich möchte also mehr über binäre Suche verstehen, weil ich nicht wirklich verstehe. Eine binäre Suche erfordert eine Voraussetzung, dass ein Array sortiert ist. Ich habe das Recht? Es scheint, als ob eine Methode diese Voraussetzung überprüfen und eine Ausnahme auswerfen sollte, wenn sie nicht erfüllt ist. Aber warum ist die Überprüfung der Voraussetzung eine schlechte Idee?

Answer 1

Es ist eine schlechte Idee, weil das Überprüfen der Daten sortiert wird n Schritte. Die ganze Suche geht darum log(n) Schritte.
Wenn Sie überprüfen, können Sie auch eine lineare Suche durchführen.

Answer 2

Der springende Punkt einer binären Suche ist, dass Sie, da die Daten bereits sortiert sind, schnell die gewünschten Informationen finden können.

Nehmen Sie das Telefonbuch, das nach Nachnamen sortiert wird.

Wie finden Sie jemanden im Telefonbuch? Sie öffnen es für eine Seite, von der Sie annehmen, dass sie genau das ist, was Sie wollen, und dann beginnen Sie die Seiten.

Aber Sie drehen nicht jedes Mal eine Seite um, wenn Sie viel verpasst haben, drehen Sie ein paar Seiten um und drehen dann schließlich eine nacheinander, bis Sie schließlich eine einzelne Seite betrachten.

Dies ist, was binäre Suche macht. Da die Daten sortiert sind, weiß sie, dass sie viel überspringen und einen weiteren Look ausführen kann, und es wird sich auf die gewünschten Informationen konzentrieren.

Eine binäre Suche führt 1 Vergleich für jede doppelte Anzahl von Elementen durch. Eine 1024 -Element -Sammlung würde also rund 10 Vergleiche erfordern, um Ihre Informationen zu finden oder zumindest herauszufinden, dass sie nicht da ist.

Wenn Sie vor der Ausführung der tatsächlichen Binärsuche einen vollständigen Durchlauf durchführen, um zu überprüfen, ob die Daten sortiert sind, können Sie genauso gut einen Scan für die Informationen durchführen. Eine vollständige Durchlauf + Die binäre Suche erfordert N + log2 n Operationen. Für 1024 Elemente würde sie rund 1034 Vergleiche erfordern, während ein einfacher Scan für die Informationen im Durchschnitt die Hälfte erfordern, was 512 ist.

Wenn Sie also nicht garantieren können, dass die Daten sortiert sind, sollten Sie keine binäre Suche verwenden, da sie durch einen einfachen Scan übertroffen werden.

---

Bearbeiten: Ich werde dies jedoch sagen, Sie könnten einen nur Debugg-Code-Schritt hinzufügen, um dies zu überprüfen, um Fehler in dem Code zu fangen, der die Daten für die binäre Suche vorbereiten soll, aber dies aufgrund dessen, was ich oben geschrieben habe, wissen. Dies wird die Gesamtlaufzeit erheblich erhöhen. Je nachdem, was Sie mit dieser Überprüfung tun möchten, möchten Sie sie möglicherweise hinzufügen oder nicht. Aber es sollte nicht im Freigaberocode vorhanden sein.

Answer 3

Yep, eine binäre Suche umfasst 0 (log n) Schritte und das Überprüfen der gesamten Sequenz ist sortiert. 0 (n) Schritte umfasst. Aus meiner Sicht ist es gut, es im Debug -Modus zu überprüfen, nicht während der Veröffentlichung.

Answer 4

Binäre Suche Angenommen, dass Eingabedaten sortiert werden. Also hier haben Sie Recht.

Überprüfen Sie jetzt im Allgemeinen, ob Daten einige Zeit sortiert werden. Die Ausführung vor der Suche nach jeder Suche würde also wirklich ineffizient machen.

Mehr Details.

Angenommen, 'n' ist die Menge Ihrer Daten.

Binäre Suche Bedürfnisse O(log(n)) Betrieb im schlimmsten Fall, um ein Element zu finden. Stellen Sie sicher, dass die Daten sortiert werden müssen O(n) Operationen.

Also, wenn wir die Voraussetzung jedes Mal nach sehr groß überprüfen werden n Wir werden die meiste Zeit mit der Überprüfung der Voraussetzung anfangen als die tatsächliche Suche.

Und es ist nicht so schwer zu sagen, wann Sie einen solchen Effekt sehen werden. Ich habe gerade berechnet, wie viel Zeit Sie für die Vorhöfe im Vergleich zu tatsächlicher Suche verbringen werden

• Für 1 Element verbringen Sie keine Zeit mit der Suche.
• Für 2 Elemente geben Sie 50% für die Suche aus.
• Für 5 Elemente, die Sie 46% für die Suche ausgeben
• Für 20 Elemente geben Sie 22% für die Suche aus.
• Für 100 Elemente geben Sie 7% für die Suche aus.

Usw. In jedem Fall wird pünktlich für die Voraussetzung für die Voraussetzung ausgegeben.

Answer 5

Zusätzlich zu dem, was alle anderen über die Laufzeit (O (n) sagten, um alle Elemente gegen O (log (n)) zu überprüfen, um binäre Suche auszuführen.)

Ich denke, Sie verstehen die Idee einer Voraussetzung. Vorkonditionen und Post-Konditionen sind ein Vertrag. Wenn Ihre Voraussetzung wahr ist und Sie Ihren Algorithmus ausführen, wird Ihre Post -Bedingung wahr sein. Wenn Ihre Voraussetzung falsch ist, machen Sie keine Garantien für die Post -Bedingung.

Grundsätzlich sagt die binäre Suche Folgendes aus: Wenn die von Ihnen vorhandenen Daten bereits sortiert sind, kann ich Ihnen die Position eines bestimmten Datenteils mitteilen oder wenn sie nicht vorhanden sind, indem Sie ungefähr Protokoll (n) Überprüfungen durchführen. Wenn die Daten nicht sortiert sind, mache ich keine Garantien für meine Antwort.

Die Arbeit, die Sie von Ihrer Vorkondition zu Ihrer Post-Kondition führt, wenn Ihr Algorithmus. In diesem Fall binäre Suche.

Answer 6

Die ursprüngliche Frage setzt voraus, dass Sie eine binäre Suche nach einer Datenerfassung verwenden. Das ist nicht immer der Fall. Oft versuchen Sie nur, eine Zahl in einem Intervall zu berechnen.

Angenommen, Sie versuchen, die optimale Geschwindigkeitseinstellung für einen Lüfter zu berechnen. Aus irgendeinem Grund können Sie keinen Ausdruck geschlossener Form finden, sodass Sie den Luftstrom mit unterschiedlichen Geschwindigkeitseinstellungen simulieren.

Angenommen, der Lüfter kann mit einer Geschwindigkeit von 0 U / min bis 5000 U / min ausgeführt werden, müssen Sie eigentlich keine Liste möglicher Geschwindigkeiten generieren. Bei jedem Schritt der binären Suche finden Sie nur den Durchschnitt des vorherigen Minimums und maximal.