Why prefer start + (end – start) / 2 over (start + end) / 2 when calculating the middle of an array?

by

There are three reasons.

First of all, start + (end - start) / 2 works even if you are using pointers, as long as end - start doesn’t overflow1.

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

Second of all, start + (end - start) / 2 won’t overflow if start and end are large positive numbers. With signed operands, overflow is undefined:

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

(Note that end - start may overflow, but only if start < 0 or end < 0.)

Or with unsigned arithmetic, overflow is defined but gives you the wrong answer. However, for unsigned operands, start + (end - start) / 2 will never overflow as long as end >= start.

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

Finally, you often want to round towards the start element.

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

Footnotes

1 According to the C standard, if the result of pointer subtraction is not representable as a ptrdiff_t, then the behavior is undefined. However, in practice, this requires allocating a char array using at least half the entire address space.

More Related Contents:

  1. Algorithm to find the smallest number in an array in C [closed]
  2. Recursive C function
  3. Fast way to tokenize a string in c
  4. Finding target sum of two numbers in array
  5. How to remove blank spaces from buffer [closed]
  6. What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?
  7. hash function for string
  8. Algorithm: efficient way to remove duplicate integers from an array
  9. What is the fastest substring search algorithm?
  10. how to rasterize rotated rectangle (in 2d by setpixel)
  11. Point in Polygon Algorithm
  12. What common algorithms are used for C’s rand()?
  13. Matrix multiplication: Small difference in matrix size, large difference in timings
  14. Enumerate factors of a number directly in ascending order without sorting?
  15. Project Euler Question 14 (Collatz Problem)
  16. How do you print the EXACT value of a floating point number?
  17. Time complexity of a recursive algorithm
  18. How to find largest triangle in convex hull aside from brute force search
  19. Finding all the unique permutations of a string without generating duplicates
  20. Print all the permutations of a string in C
  21. Given an audio stream, find when a door slams (sound pressure level calculation?)
  22. find if 4 points on a plane form a rectangle?
  23. Linked list recursive reverse
  24. Generating a uniform distribution of INTEGERS in C
  25. signed and unsigned arithmetic implementation on x86
  26. Reductions in parallel in logarithmic time
  27. Finding out the duplicate element in an array
  28. Does C have any tools for doing string addition?
  29. Extend a line segment a specific distance
  30. QuickSort and Hoare Partition

Leave a Comment