Pourquoi la recherche binaire est-elle appelée recherche binaire?

J'ai entendu plusieurs explications possibles, donc je voudrais une référence fiable.

Mise à jour 05.19: Je m'intéresse à la question parce qu'un de mes étudiants a écrit dans sa thèse que le nom vient de l'explication ci-dessous (1). Jusqu'à présent, je pensais / entendais que cela venait de l'explication (2). Je me sentirais mal à la fois d'avoir laissé la mauvaise chose dans sa thèse, ainsi que de lui dire de la retirer si cela pouvait être juste.

(1) Considérons la recherche d'un entier dans l'intervalle . Nous pouvons le trouver en utilisant n questions en demandant à l'étape i le i t h chiffre binaire du nombre.$[0,2^{n-1}]$$n$$i$$i^{th}$

(2) Si nous avons un espace de recherche avec éléments, nous pouvons trouver un élément inconnu par des questions qui divisent à plusieurs reprises la partie restante de l'espace en deux .$2^n$

Et oui, je sais que (2) peut donner le même algorithme que (1) mais ce n'est pas le point ici. (2) peut également être appliqué pour des problèmes plus généraux.

L'explication (2) est une bonne explication.

(2) est la meilleure explication des deux, car elle s'applique généralement à toutes les utilisations de la recherche binaire, pas seulement à une instance spécifique. (1) n'est pas une manière déraisonnable d'y penser - ce n'est tout simplement pas aussi général ou complet que (2).

Je ne pense pas que vous ayez besoin de vous sentir obligé d'exiger que l'étudiant corrige cette affirmation. Ce ne serait pas gênant si un étudiant donne des explications (1) dans sa thèse, vous n'avez donc pas besoin de vous sentir mal. Mais si vous voulez leur apprendre quelque chose, vous pouvez leur expliquer l'explication (2) et comment la recherche binaire est plus générale et pourquoi le nom "recherche binaire" est également raisonnable pour l'algorithme général. Mais c'est un point mineur et non quelque chose que je considérerais comme problématique ou gênant s'ils laissaient les choses telles quelles.

Selon Wikipedia, la recherche binaire concerne la recherche dans un tableau de valeurs triées.

Le concept plus général de diviser pour mieux régner en divisant l'espace de recherche de façon répétée est appelé recherche dichotomique (littéralement: "qui coupe en deux"). L'utilisation de la dichotomie peut être envisagée dans d'autres contextes, tant que vous avez quelque chose à diviser. C'est en fait la première expression que j'ai apprise (au lycée, je pense, et c'était il y a longtemps), y compris dans les cas où vous pourriez l'appeler binaire.

Afaik, "dichotomique" n'implique pas que les deux parties soient (presque) égales.

$2^n$

Dichotomique est clairement le terme le plus général, mais il peut sembler pédant pour certains qui pourraient à la place utiliser incorrectement le binaire.

Votre exemple (1) est étrangement énoncé, car on ne demande pas consciemment des chiffres binaires, mais plutôt une comparaison avec la médiane d'un intervalle. Mais il pourrait être qualifié de binaire.

L'exemple de Youe (2) n'est pas clair. Le fractionnement en deux devrait être appelé dichotomique. Maintenant, comme vous semblez émettre l'hypothèse (étrangement) d'une façon de faire 2 parties égales, je ne suis pas sûr.

Mais un jeu de devinettes, où les gens posent des questions auxquelles on répond par oui ou par non, est clairement dichotomique.

Ma propre supposition, aucune référence donnée:

L'expression originale était probablement «dichotomique», mais avec la popularité des systèmes binaires, des ordinateurs binaires, etc., le terme «binaire» est devenu plus populaire.

Un autre facteur qui a pu jouer un rôle important est que la recherche binaire (ainsi que dichotomique) est basée sur des choix binaires. Désormais, l'expression « choix dichotomique » existe, mais est beaucoup moins utilisée que « choix binaire », qui apparaît environ 6 fois plus souvent sur le Web.

Cela a donc peut-être influencé cela. Nous devons nous rappeler que bien que nous soyons largement immergés dans le nombre binaire (je veux dire nous, informaticien), la plupart des gens ne sont pas et ne sont pas concernés par les nombres binaires, mais parleront facilement d'un choix binaire. Il est vrai que la recherche binaire est un sujet pour les informaticiens, mais à moins d'une référence fiable au contraire, je ne croirai pas qu'elle provient directement des nombres binaires.

Knuth (V.3 Pg. 82) donne Mauchly comme source de recherche binaire; il est utilisé pour trouver le point d'insertion lors d'un tri qui mélange ensuite les éléments vers l'avant pour créer une vacance, dans un processus appelé insertion binaire.

Donc (2) serait valide, mais je ne peux pas voir le document original; il est masqué ici: https://books.google.com/books?id=A6EEAQAAIAAJ&focus=searchwithinvolume&q=sorting+and+collating

J'ai essayé de rechercher la référence Mauchly citée par Knuth mais ma bibliothèque semble avoir égaré leur copie.

En attendant, considérez les citations précoces suivantes pour la "recherche binaire":

• Halpern, Mark. " Tables à largeur variable avec fonction de recherche binaire. " Communications de l'ACM 1.2 (1958): 1-4.

  La famille de sous-programmes décrits dans ce rapport a été conçue pour créer, rechercher et maintenir des tables qui doivent contenir des entrées de différentes longueurs, tout en pouvant être recherchées par partition, ou recherche «binaire».

• Nagler, H. " Une estimation de l'efficacité relative de deux méthodes de tri internes. " Communications de l'ACM 3.11 (1960): 618-620.

  Ce rapport concerne l'IBM 705, modèles I et II. Il s'agit d'une étude du temps machine requis par deux méthodes de tri internes, la fusion bidirectionnelle conventionnelle, et une forme de la recherche binaire, qui est due à D. Mordy, d'IBM Corporation.

• Petersen, TL PROGRAMME DE SYNTHÈSE DES VÉHICULES DE RÉENTRÉE. No. STL / TR-60-0000-09103 (lien pdf) . 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$

Je noterai comment la première citation de 1958 utilise des guillemets autour de "binaire" mais par la troisième citation en 1960, une recherche binaire est mentionnée sans autre description ou explication. L'allusion à la «recherche par partition» tendrait à suggérer que l'explication 2) est plus proche, mais une vérification plus approfondie est nécessaire.