binäre Suchmuster Details der Implementierung/Nutzung Fragen

Question

Die folgende SO url bietet einige gute Praxisbeispiele für Big O-Notation:

What does O(log n) mean exactly?

Ich bin speziell Interesse an dem folgenden Beispiel für eine binäre Suche zur Verfügung gestellt :

„O (log n): den Namen einer Person gegeben, einen zufälligen Punkt etwa auf halbem Weg durch den Teil des Buches die Überprüfung der Telefonnummer finden Sie gesucht haben noch nicht von Kommissionierung, dann, um zu sehen, ob der Name der Person ist Dann wiederhole den Vorgang etwa auf halbem Weg durch den Teil des Buches, in dem der Der Name der Person liegt. (Dies ist eine binäre Suche nach dem Namen einer Person.)“

Es gibt ein paar Dinge über das, was ich bin unklar:

• Hat ein Lehrbuch binäre Suche starten, indem auf die exakt auf halbem Wege der Suche Punkt eines Arrays? Wenn es eine gerade Anzahl von Elementen im Array gibt, sollte ein binärer Suchalgorithmus das untere oder höhere Element zufällig auswählen?

• Sucht eine Textbuch-Binärsuche eine Suche nach bestimmten Datenpunkten auf halbem Weg Oder sucht es nach Clustergruppen von Datenpunkten, um eine bessere Effizienz zu erzielen, oder unterstützt es auch ein binäres Suchmuster? einer dieser Ansätze?

• Kann die binäre Suche auf sortierte oder unsortierte Arrays angewendet werden? Oder wird es immer empfohlen, ein Array vor dem Ausführen einer binären Suche programmgesteuert zu sortieren?

Answer 1

Es gibt bestimmte Dinge, die das Beispiel nicht richtig erklärt. Stellen Sie sich vor, dass es sich um ein Wörterbuch handelt, in dem Sie nach einem Namen suchen. Nehmen wir an, Sie suchen nach "John". Die (n/2) -te Seite gibt Ihnen Namen beginnend mit dem Buchstaben L (sagen Seite X). Also ignorierst du alles, was von dieser Seite ausgeht und weiter, da du weißt, dass diese Seite und die weiteren nicht das haben können, wonach du suchst. Jetzt ist Ihr Such-Set auf die Suche von Seite 1 auf Seite X beschränkt. Führen Sie den gleichen Schritt aus, bei dem Sie jedes Mal, wenn Sie eine Seite auswählen, n/2 Elemente des Such-Sets ignorieren.

Also, aus der Erklärung hatte ich gegeben:

1.) Wenn n gerade/ungerade ist, nur wählen, was Sie von n/2 erhalten. Sie werden in der nächsten Iteration entweder Seite 1 bis (n/2) -1 (oder) Seite (n/2) +1 bis n betrachten. Es besteht also keine Gefahr, hier irgendwelche Elemente zu überspringen.

2.) Bei jeder Iteration betrachten Sie die gesamte Suchmenge. Der Unterschied zwischen Suchsätzen von Iteration i zu i + 1 ist, dass die Anzahl der Elemente um die Hälfte reduziert wird.

3.) Eine der Voraussetzungen für BS ist, dass wir eine sortierte Liste von Items in Betracht ziehen sollten. Deshalb habe ich in meiner Erklärung ein Wörterbuch verwendet.

Und der Grund, warum diese Operation ist O (logn) ist, weil Sie die Liste der Elemente jedes Mal um die Hälfte reduzieren. Stellen Sie sich vor, Sie haben 32 Artikel in der Liste. Die Anzahl der Iterationen, die erforderlich sind, um die Antwort hier zu finden, ist 5 (32 in der ersten Iteration auf 16 reduziert, 16 in der zweiten Iteration auf 8 reduziert usw.).Wie Sie sehen können, ist die Beziehung zwischen 32 und 5 log 32 (Basis 2) = 5