¿Por qué preferir start + (end - start) / 2 sobre (start + end) / 2 al calcular el centro de una matriz?

He visto a programadores usar la fórmula

mid = start + (end - start) / 2

en lugar de usar la fórmula más simple

mid = (start + end) / 2

para encontrar el elemento del medio en la matriz o lista.

¿Por qué usan el anterior?

Hay tres razones

En primer lugar, start + (end - start) / 2funciona incluso si está utilizando punteros, siempre que end - startno se desborde ¹ .

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

En segundo lugar, start + (end - start) / 2¿No desbordamiento si starty endson grandes números positivos. Con operandos firmados, el desbordamiento no está definido:

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

(Tenga en cuenta que end - startpuede desbordarse, pero solo si start < 0o end < 0.)

O con aritmética sin signo, se define el desbordamiento pero le da la respuesta incorrecta. Sin embargo, para operandos sin firmar, start + (end - start) / 2nunca se desbordará mientras end >= start.

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

Finalmente, a menudo quieres redondear hacia el startelemento.

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

Notas al pie

¹ Según el estándar C, si el resultado de la resta del puntero no es representable como a ptrdiff_t, entonces el comportamiento es indefinido. Sin embargo, en la práctica, esto requiere asignar una charmatriz utilizando al menos la mitad del espacio de direcciones completo.

Podemos tomar un ejemplo simple para demostrar este hecho. Supongamos que en una determinada matriz grande , estamos tratando de encontrar el punto medio del rango [1000, INT_MAX]. Ahora, INT_MAXes el valor más grande que intpuede almacenar el tipo de datos. Incluso si 1se agrega a esto, el valor final será negativo.

Además, start = 1000y end = INT_MAX.

Utilizando la fórmula: (start + end)/2,

el punto medio será

(1000 + INT_MAX)/2= -(INT_MAX+999)/2, que es negativo y puede dar un error de segmentación si intentamos indexar utilizando este valor.

Pero, usando la fórmula (start + (end-start)/2), obtenemos:

(1000 + (INT_MAX-1000)/2)= (1000 + INT_MAX/2 - 500)= (INT_MAX/2 + 500) que no se desbordará .

Para agregar a lo que otros ya han dicho, el primero explica su significado más claramente para aquellos con una mentalidad menos matemática:

mid = start + (end - start) / 2

se lee como:

mediados es igual a inicio más la mitad de la longitud.

mientras:

mid = (start + end) / 2

se lee como:

mediados es igual a la mitad del inicio más el final

Lo que no parece tan claro como el primero, al menos cuando se expresa así.

como señaló Kos, también puede leer:

mediados es igual al promedio de inicio y fin

Lo cual es más claro pero aún no, al menos en mi opinión, tan claro como el primero.

start + (end-start) / 2 puede evitar un posible desbordamiento, por ejemplo start = 2 ^ 20 y end = 2 ^ 30