Pourquoi le milieu ne s'écrit pas $(g+d)/2$

Elles diffèrent dès que $g+d$ dépasse la capacité du type entier — donc jamais en mathématiques, et bel et bien en machine. Mesuré en C avec des int de $32$ bits, pour $g=2000000000$ et $d=2100000000$ :

Avec INT_MAX $=2147483647$, la somme $4,1\cdot 10^9$ déborde et le résultat est négatif : l'indice obtenu n'appartient même pas à $[g,d]$. La recherche accède alors hors du tableau — un défaut du chapitre chap:langage-c, ici au cœur d'un algorithme réputé simple.

Pourquoi la seconde forme est sûre. On a $0\le d-g\le d$, donc $(d-g)/2$ tient dans le type ; et $g+(d-g)/2\le d$ tient aussi. Aucune expression intermédiaire ne sort de $[g,d]$, et c'est la propriété qu'on cherche.

Deux remarques pour finir. En OCaml, les entiers font $63$ bits et le débordement ne se produirait qu'au-delà de $4,6\cdot 10^{18}$ : le défaut est invisible sur la version OCaml du cours, et bien réel sur sa transcription en C. Et sur des entiers non signés, où le débordement est défini modulo $2^{32}$, les deux expressions redonnent la même valeur $2050000000$ — ce qui a été vérifié. Un défaut qui dépend du type, du langage, et de la taille des données : c'est le pire genre.