Pourquoi préférer start + (end - start) / 2 à (start + end) / 2 pour calculer le milieu d'un tableau ?

Question

J'ai vu des programmeurs utiliser la formule

mid = start + (end - start) / 2

au lieu d'utiliser la formule plus simple

mid = (start + end) / 2

pour trouver l'élément central d'un tableau ou d'une liste.

Pourquoi utilisent-ils la première ?

Answer 1

Il y a trois raisons.

Tout d'abord, start + (end - start) / 2 fonctionne même si vous utilisez des pointeurs, du moment que end - start ne déborde pas 1 .

int *start = ..., *end = ...;
int *mid = start + (end - start) / 2; // works as expected
int *mid = (start + end) / 2;         // type error, won't compile

Deuxièmement, start + (end - start) / 2 ne débordera pas si start et end sont de grands nombres positifs. Avec des opérandes signés, le dépassement est indéfini :

int start = 0x7ffffffe, end = 0x7fffffff;
int mid = start + (end - start) / 2; // works as expected
int mid = (start + end) / 2;         // overflow... undefined

(Notez que end - start peut déborder, mais seulement si start < 0 ou end < 0 .)

Ou avec l'arithmétique non signée, le dépassement est défini mais vous donne la mauvaise réponse. Cependant, pour les opérandes non signés, start + (end - start) / 2 ne débordera jamais tant que end >= start .

unsigned start = 0xfffffffeu, end = 0xffffffffu;
unsigned mid = start + (end - start) / 2; // works as expected
unsigned mid = (start + end) / 2;         // mid = 0x7ffffffe

Enfin, vous souhaitez souvent arrondir vers le start élément.

int start = -3, end = 0;
int mid = start + (end - start) / 2; // -2, closer to start
int mid = (start + end) / 2;         // -1, surprise!

Notes de bas de page

1 Selon la norme C, si le résultat de la soustraction d'un pointeur n'est pas représentable en tant que ptrdiff_t alors le comportement est indéfini. Cependant, en pratique, cela nécessite l'allocation d'un objet char utilisant au moins la moitié de l'espace d'adressage.

Answer 2

Nous pouvons prendre un exemple simple pour démontrer ce fait. Supposons que dans un certain grand site nous essayons de trouver le point médian de l'intervalle [1000, INT_MAX] . Maintenant, INT_MAX est la plus grande valeur que l int que le type de données peut stocker. Même si 1 est ajouté à cela, la valeur finale deviendra négative.

Aussi, start = 1000 et end = INT_MAX .

En utilisant la formule : (start + end)/2 ,

le point médian sera

(1000 + INT_MAX)/2 = -(INT_MAX+999)/2 qui est négatif et peut donner lieu à un défaut de segmentation si on essaie d'indexer en utilisant cette valeur.

Mais, en utilisant la formule, (start + (end-start)/2) on obtient :

(1000 + (INT_MAX-1000)/2) = (1000 + INT_MAX/2 - 500) = (INT_MAX/2 + 500) qui ne débordera pas .

Answer 3

Pour ajouter à ce que d'autres ont déjà dit, la première explique sa signification plus clairement aux personnes ayant moins d'esprit mathématique :

mid = start + (end - start) / 2

se lit comme :

Le milieu est égal au début plus la moitié de la longueur.

alors que :

mid = (start + end) / 2

se lit comme :

le milieu est égal à la moitié du début plus la fin

Ce qui ne semble pas aussi clair que le premier, du moins lorsqu'il est exprimé de cette manière.

comme l'a souligné Kos, il peut aussi être lu :

le milieu est égal à la moyenne du début et de la fin

Ce qui est plus clair mais toujours pas, du moins à mon avis, aussi clair que le premier.

Answer 4

Début + (fin-début) / 2 peut éviter un éventuel dépassement, par exemple début = 2^20 et fin = 2^30