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

5 minutos de lectura

avatar de usuario
pallavi chauhan

He visto 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 medio en la matriz o lista.

¿Por qué usan el anterior?

  • Suposición salvaje: (start + end) podría desbordarse, mientras (end - start) no poder.

    – cadaniluk

    31/07/2016 a las 20:15

  • porque esto último no funciona cuando start y end son puntero.

    – ensc

    31/07/2016 a las 20:20

  • start + (end - start) / 2 también tiene significado semántico: (end - start) es la longitud, entonces esto dice: start + half the length.

    – njzk2

    1 de agosto de 2016 a las 2:16

  • @LưuVĩnhPhúc: ¿Esta pregunta no tiene las mejores respuestas y la mayor cantidad de votos? Si es así, las otras preguntas probablemente deberían cerrarse como un dup de esta. La antigüedad de los postes es irrelevante.

    – Nisse Engström

    2 de agosto de 2016 a las 12:08

avatar de usuario
dietrich epp

Hay tres razones.

Ante todo, start + (end - start) / 2 funciona incluso si está utilizando punteros, siempre que end - start no se desborda1.

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

Segundo, start + (end - start) / 2 no se desbordará si start y end son números positivos grandes. 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 - start puede desbordarse, pero sólo si start < 0 o end < 0.)

O con aritmética sin signo, el desbordamiento está definido pero le da la respuesta incorrecta. Sin embargo, para operandos sin signo, start + (end - start) / 2 nunca 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 desea redondear hacia el start elemento.

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

1 De acuerdo con el estándar C, si el resultado de la resta del puntero no se puede representar como un ptrdiff_t, entonces el comportamiento es indefinido. Sin embargo, en la práctica, esto requiere asignar un char matriz utilizando al menos la mitad del espacio de direcciones completo.

  • resultado de (end - start) en el signed int el caso no está definido cuando se desborda.

    – ensc

    31/07/2016 a las 20:52

  • ¿Puedes probar que end-start no se desbordará? AFAIK si tomas un negativo start debería ser posible hacer que se desborde. Claro, la mayoría de las veces cuando calculas el promedio sabes que los valores son >= 0

    – Bakuriu

    31 de julio de 2016 a las 21:28


  • @Bakuriu: Es imposible probar algo que no es cierto.

    -Dietrich Epp

    31 de julio de 2016 a las 23:07

  • Es de particular interés en C, ya que la resta de puntero (según el estándar) se rompe por diseño. Las implementaciones están permitidas para crear arreglos tan grandes que end - start no está definido, porque los tamaños de los objetos no están firmados, mientras que las diferencias de puntero están firmadas. Entonces end - start “funciona incluso usando punteros”, siempre que también mantenga el tamaño de la matriz a continuación PTRDIFF_MAX. Para ser justos con el estándar, eso no es una gran obstrucción en la mayoría de las arquitecturas, ya que es la mitad del tamaño del mapa de memoria.

    –Steve Jessop

    1 de agosto de 2016 a las 11:03


  • @Bakuriu: Por cierto, hay un botón de “editar” en la publicación que puede usar para sugerir cambios (o hacerlos usted mismo) si cree que me he perdido algo o si algo no está claro. Solo soy humano, y esta publicación ha sido vista por más de dos mil pares de ojos. El tipo de comentario, “Deberías aclarar…” realmente me molesta.

    -Dietrich Epp

    1 de agosto de 2016 a las 14:02

avatar de usuario
Shubham

Podemos tomar un ejemplo simple para demostrar este hecho. Supongamos que en cierto grande matriz, estamos tratando de encontrar el punto medio del rango [1000, INT_MAX]. Ahora, INT_MAX es el mayor valor el int tipo de datos puede almacenar. Incluso si 1 se suma a esto, el valor final será negativo.

También, start = 1000 y end = INT_MAX.

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

el punto medio sera

(1000 + INT_MAX)/2 = -(INT_MAX+999)/2cual es negativo y puede dar falla de segmentación si tratamos de indexar usando 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 desborda.

  • Si sumas 1 a INT_MAXel resultado no será negativo, sino indefinido.

    – celtschk

    01/08/2016 a las 21:46

  • @celtschk Teóricamente, sí. Prácticamente se envolverá muchas veces al pasar de INT_MAX para -INT_MAX. Sin embargo, es un mal hábito confiar en eso.

    – Mástil

    2 de agosto de 2016 a las 9:46

avatar de usuario
El codificador letal

Para agregar a lo que otros ya han dicho, el primero explica su significado más claro para aquellos menos matemáticos:

mid = start + (end - start) / 2

se lee como:

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

mientras que:

mid = (start + end) / 2

se lee como:

medio es igual a la mitad de inicio más final

Lo cual no parece tan claro como el primero, al menos expresado así.

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

mid es igual al promedio de inicio y final

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

  • Veo tu punto, pero esto realmente es una exageración. Si ve “e – s” y piensa en “longitud”, entonces seguramente verá “(s+e)/2” y pensará en “promedio” o “medio”.

    – Djechlin

    1 de agosto de 2016 a las 22:57


  • @djechlin Los programadores son malos en matemáticas. Están ocupados haciendo su trabajo. No tienen tiempo para asistir a las clases de matemáticas.

    – Pequeño alienígena

    2 de agosto de 2016 a las 5:01

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

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad