Gibt es einen effizienteren Suchfaktor als den Mittelpunkt für die binäre Suche?

Question

Die naive binäre Suche ist ein sehr effizienter Algorithmus: Sie nehmen den Mittelpunkt Ihrer oberen und unteren Punkte in einem sortierten Array und passen Ihren oberen oder unteren Punkt entsprechend an. Dann berechnen Sie Ihren Endpunkt neu und iterieren, bis Sie Ihren Zielwert finden (oder natürlich nicht.)

Nun, ganz klar, wenn Sie den Mittelpunkt nicht verwenden, führen Sie ein gewisses Risiko für das System ein. Angenommen, Sie verschieben Ihr Suchziel vom Mittelpunkt weg und Sie erstellen zwei Seiten - ich nenne sie eine große Seite und eine kleine Seite. (Es spielt keine Rolle, ob die Verschiebung zu hoch oder zu niedrig ist, weil es symmetrisch wäre.) Das Risiko besteht darin, dass Ihr Suchraum größer ist, als Sie es wären: Sie müssen die große Seite suchen, die ist größer. Aber die Belohnung ist, dass, wenn Sie Ihren Suchraum treffen, kleiner ist.

Es fällt mir auf, dass die Anzahl der belasteten Räume gleich ist und (ohne Muster, von denen ich annehme, dass es keine gibt) die Wahrscheinlichkeit, dass ein Element höher und niedriger als der Mittelpunkt ist, gleich ist. Das Risiko besteht also darin, dass es zwischen dem neuen Ziel und dem Mittelpunkt liegt.

Jetzt, da die Anzahl der Leerzeichen den Suchraum beeinflusst und der Suchraum logarithmisch gemessen wird, scheint es mir, wenn ich verwendet habe, sagen wir 1/4 und 3/4 für unsere Suchräume, die ich geschnitten habe Log von dem kleinen Raum in der Mitte, wo der große Raum nur um etwa 0,6 oder 0,7 gestiegen ist.

Also mit all dem im Hinterkopf: Gibt es eine effizientere Art der Durchführung einer binären Suche als nur die Verwendung des Mittelpunkts?

Answer 1

Wir stimmen zu, dass der Suchschlüssel wahrscheinlich an der Position im Array — ist, andernfalls würden wir einen Algorithmus basierend auf unserer speziellen Kenntnis des Standorts entwerfen wollen. Wir können also nur wählen, wo wir das Array jedes Mal aufteilen. Wenn wir eine Zahl 0 < x < 1 wählen und das Array dort aufteilen, ist die Wahrscheinlichkeit, dass es auf der linken Seite ist, x und die Wahrscheinlichkeit, dass es auf der rechten Seite ist, ist 1-x. Im ersten Fall verkürzen wir die Anordnung um den Faktor x und in der zweiten um den Faktor 1-x. Wenn wir das viele Male machen würden, hätten wir ein Produkt aus vielen dieser Faktoren, und deshalb ist der "richtige" Durchschnitt hier das geometrische Mittel. In diesem Sinne ist die durchschnittliche Abnahme pro Schritt x mit Gewicht x und 1-x mit Gewicht 1-x für eine Summe von x^x * (1-x)^(1-x).

Wann wird das minimiert? Wenn dies der mathematische Stackexchange wäre, würden wir Derivate (mit der Produktregel, Kettenregel und Exponentenregel) nehmen, sie auf Null setzen und lösen. Aber das ist stackoverflow, so dass wir es grafisch darstellen:

Sie können sehen, dass je weiter Sie von 1/2 kommen, desto schlimmer werden Sie. Zum besseren Verständnis empfehle ich Informationstheorie oder Infinitesimalrechnung, die interessante und ergänzende Perspektiven dazu haben.