We want an integer midpoint of two values l and r, with l <= r. Here, the required answer is their exact mathematical average with any fractional part discarded toward zero. For nonnegative array indices, this means rounding the average down.

Consider these four expressions:

/* A */ (l + r) / 2
/* B */ l + (r - l) / 2
/* C */ ((long long)l + r) / 2
/* D */ l / 2 + r / 2 + (l % 2 + r % 2) / 2

Both variables have type int. Assume a 32-bit signed int, from -2147483648 through 2147483647, and a 64-bit signed long long. The cast in C converts l before the addition, so that addition is performed as long long.

Integer division discards the fractional part toward zero. The remainder satisfies x = (x / 2) * 2 + x % 2; it can be negative when x is negative. A signed operation that exceeds its type’s range has undefined behavior.

Midpoints are used, for example, to divide a range of array indices into two parts. The questions below specify which values l and r can take.