Warum heißt binäre Suche binäre Suche?

Ich habe mehrere mögliche Erklärungen gehört, daher hätte ich gerne eine vertrauenswürdige Referenz.

Update 05.19: Ich bin an der Frage interessiert, weil einer meiner Studenten in seiner Diplomarbeit geschrieben hat, dass der Name aus der folgenden Erklärung stammt (1). Bis jetzt habe ich gedacht / gehört, dass es aus der Erklärung kommt (2). Ich würde mich schlecht fühlen, wenn ich das Falsche in seiner These zulassen würde und ihm sagen würde, er solle es entfernen, wenn es richtig wäre.

(1) Betrachten Sie die Suche nach einer ganzen Zahl im Intervall . Wir können es anhand von n Fragen finden, indem wir in Schritt i die i t h Binärziffer der Zahl fragen .$[0,2^{n-1}]$$n$$i$$i^{th}$

(2) Wenn wir einen Suchraum mit Elementen haben, können wir ein unbekanntes Element durch Fragen finden, die den verbleibenden Teil des Raums wiederholt in zwei Teile teilen .$2^n$

Und ja, ich weiß, dass (2) den gleichen Algorithmus wie (1) geben kann, aber das ist hier nicht der Punkt. (2) kann auch für allgemeinere Probleme angewendet werden.

Erklärung (2) ist eine gute Erklärung.

(2) ist die bessere Erklärung der beiden, da sie allgemein für alle Verwendungen der binären Suche gilt, nicht nur für eine bestimmte Instanz. (1) ist keine unvernünftige Art, darüber nachzudenken - es ist einfach nicht so allgemein oder vollständig wie (2).

Ich glaube nicht, dass Sie sich verpflichtet fühlen müssen, vom Schüler die Korrektur dieser Aussage zu verlangen. Es wäre nicht peinlich, wenn ein Student in seiner Arbeit eine Erklärung (1) geben würde, damit Sie sich nicht schlecht fühlen müssen. Wenn Sie ihnen jedoch etwas beibringen möchten, können Sie ihnen die Erklärung (2) erläutern und erläutern, wie die binäre Suche allgemeiner ist und warum der Name "binäre Suche" auch für den allgemeinen Algorithmus angemessen ist. Aber es ist ein kleiner Punkt und nichts, was ich als problematisch oder peinlich ansehen würde, wenn sie die Dinge so lassen würden, wie sie sind.

Laut Wikipedia betrifft die binäre Suche die Suche in einem Array sortierter Werte.

Das allgemeinere Konzept der Teilung und Eroberung der Suche durch wiederholtes Aufteilen des Suchraums wird als dichotomische Suche bezeichnet (wörtlich: "das schneidet in zwei Teile "). Die Verwendung der Dichotomie kann in anderen Kontexten in Betracht gezogen werden, so wie Sie etwas zu spalten haben. Es ist tatsächlich der erste Ausdruck, den ich gelernt habe (in der High School, glaube ich, und das war vor langer Zeit), auch in Fällen, in denen Sie ihn vielleicht als binär bezeichnen möchten.

Afaik, "dichotomisch" bedeutet nicht, dass die beiden Teile (fast) gleich sind.

$2^n$

Dichotomisch ist eindeutig der allgemeinere Begriff, aber es mag für einige pedantisch klingen, die stattdessen möglicherweise binär falsch verwenden.

Ihr Beispiel (1) ist seltsamerweise angegeben, da man nicht bewusst nach Binärziffern fragt, sondern nach einem Vergleich mit dem Median eines Intervalls. Aber es könnte sich als binär qualifizieren.

Ihr Beispiel (2) ist unklar. Nur in zwei Teile zu teilen, sollte als dichotomisch bezeichnet werden. Nun, da Sie (seltsamerweise) eine Möglichkeit zu vermuten scheinen, zwei gleiche Teile herzustellen, bin ich mir nicht sicher.

Aber ein Ratespiel, bei dem Leute Fragen stellen, die mit Ja oder Nein beantwortet werden, ist eindeutig dichotomisch.

Meine eigene Vermutung, kein Hinweis gegeben:

Der ursprüngliche Ausdruck war wahrscheinlich "dichotomisch", aber mit der Popularität von Binärsystemen, Binärcomputern usw. wurde der Begriff "Binär" populärer.

Ein weiterer Faktor, der möglicherweise eine wichtige Rolle gespielt hat, ist, dass die binäre Suche (sowie die dichotomische Suche) auf binären Entscheidungen basiert. Jetzt existiert der Ausdruck " dichotome Wahl ", wird aber viel weniger verwendet als " binäre Wahl ", die im Web etwa sechsmal häufiger vorkommt.

Das könnte das also beeinflusst haben. Wir sollten uns daran erinnern, dass die meisten Menschen, obwohl wir weitgehend in Binärzahlen versunken sind (ich meine wir, Informatiker), sich nicht mit Binärzahlen befassen und sich auch nicht damit befassen, sondern leicht von einer Binärzahl sprechen werden. Es ist wahr, dass die binäre Suche ein Thema für Informatiker ist, aber ohne einen verlässlichen Hinweis auf das Gegenteil werde ich nicht glauben, dass es auf irgendeine direkte Weise von binären Zahlen stammt.

Knuth (V.3 S. 82) gibt Mauchly als Quelle für die binäre Suche an; Es wird verwendet, um die Einfügemarke während einer Sortierung zu finden, die dann Elemente vorwärts mischt, um eine freie Stelle zu schaffen, in einem Prozess, der als binäre Einfügung bezeichnet wird.

Also (2) wäre gültig, aber ich kann das Originalpapier nicht sehen; Es ist hier verdeckt: https://books.google.com/books?id=A6EEAQAAIAAJ&focus=searchwithinvolume&q=sorting+and+collating

Ich habe versucht, die von Knuth zitierte Mauchly-Referenz nachzuschlagen, aber meine Bibliothek scheint ihre Kopie verlegt zu haben.

Berücksichtigen Sie in der Zwischenzeit die folgenden frühen Zitate für "binäre Suche":

• Halpern, Mark. " Tabellen mit variabler Breite und binärer Suchfunktion. " Mitteilungen des ACM 1.2 (1958): 1-4.

  Die in diesem Bericht beschriebene Familie von Unterprogrammen wurde entwickelt, um Tabellen zu erstellen, zu suchen und zu verwalten, die Einträge unterschiedlicher Länge enthalten und dennoch nach Partition oder "binärer" Suche durchsucht werden können.

• Nagler, H. " Eine Schätzung der relativen Effizienz zweier interner Sortiermethoden. " Mitteilungen des ACM 3.11 (1960): 618-620.

  Dieser Bericht betrifft den IBM 705, Modelle I und II. Es handelt sich um eine Untersuchung der Maschinenzeit, die für zwei interne Sortiermethoden erforderlich ist, die herkömmliche bidirektionale Zusammenführung und eine Form der binären Suche, die D. Mordy von der IBM Corporation zu verdanken ist.

• Petersen, TL PROGRAMM ZUR WIEDERAUFNAHME VON FAHRZEUGSYNTHESEN. STL / TR-60-0000-09103 (pdf-Link) . TRW SPACE TECHNOLOGY LABS LOS ANGELES CA, 1960.

  ${V_0}^*$$g({V_0}^*) = 0$$g(0) = K_3 - 1$$g(K_1) = -1$${V_0}^*$$K_1$$K_3>1$$g({V_0}^*)$${V_0}^*$${V_0}^*$$0.01$

Ich werde bemerken, wie das erste Zitat von 1958 Anführungszeichen um "binär" verwendet, aber beim dritten Zitat von 1960 wird eine binäre Suche ohne weitere Beschreibung oder Erklärung erwähnt. Die Anspielung auf "Suche nach Partition" würde eher darauf hindeuten, dass Erklärung 2) näher ist, aber eine weitere Überprüfung erforderlich ist.