2

I've found that in some algorithms to find the middle point of a numeric range the next formula is used:

middle = low + ((high - low) / 2)

Yet, others use the next formula:

middle = (low + high) / 2

I've done some test and both formulas yield to the same correct middle result. My question is, do both always yield to the same result? or does any of them need to be used for specific scenarios or conditions?

If both are exactly the same, is there any reason why one would be used over the other?

API_1024
  • 123
  • Both are equivalent mathematically – Aditya Dwivedi Aug 31 '20 at 14:18
  • Yes! low + ((high - low) / 2)=(2low + (high - low))/2=(low + high) / 2 – Robert Z Aug 31 '20 at 14:19
  • If you want to be incredibly pedantic... there are some scenarios in practice where (low + high) / 2 would fail, namely in computer programming when low and high happened to be near the upper bound of their respective datatypes. You'd have an overflow error if low + high were too large. That said, this is a particularly uncommon occurrence and in most contexts you can safely ignore it. – JMoravitz Aug 31 '20 at 14:25

4 Answers4

2

While the two formulas are equivalent mathematically, the first is preferred in computer programming, because of the possibility of overflow in the second. Even though high and low are legitimate values, it is possible that high+low is too big. Then the second formula will give an incorrect value, while the first would give the correct one.

saulspatz
  • 53,131
1

Call them $m, l$ and $h$ for simplicity and we can see that $m= l+(h-l)/2 = l + h/2 -l/2=l/2 + h/2$ so both formulas are exactly the same.

CyclotomicField
  • 11,018
  • 1
  • 12
  • 29
0

$$a + \frac{b-a}{2} = \frac{2a}{2} + \frac{b-a}{2} = \frac{2a + b-a}{2} = \frac{b+a}{2}$$

TheSilverDoe
  • 29,720
0

Both those expression are mathematically equivalent. However, pay attention to floating-point arithmetics and its possible undesirable effects, such as the so-called catastrophic cancellation.

For instance, if your are working with positive numbers, it is better to use the second expression. Indeed, when high and low are nearly equal, their subtraction can lead to an important reduction in the number of significant digits.

On the other hand, the sum high+low in the last formula may overcome the computational arithmetical limit of the used class of numbers.

SigmaBoy
  • 109