Binary Search: how to determine half of the array

Question

What's the difference between this two formulas

mid = low + (high - low) / 2;


mid = (high + low) / 2;

Answer 1

In the 2nd version, if high + low is greater than the maximum value of an int (assuming high is an int) then it can overflow, invoking undefined behavior. This particular bug is solved with the 1st version.

There are still issues with the 1st version, e.g. if low is a very large negative number, the difference can still overflow.

From c++20, you should use std::midpoint for this, which handles a whole bunch of corner cases, and does the right thing for all of them.

This seemingly simple function is actually surprisingly difficult to implement, and in fact, there's an hour long talk given by Marshall Clow at cppcon 2019, that covers the implementation of just this function.

Answer 2

The first one is superior (although still not perfect, see Binary Search: how to determine half of the array):

1. It works in cases where addition is not defined for high and low but is defined for adding an interval to low. Pointers are one such example, an object of a date type can be another.

2. high + low can overflow the type. For a signed integral type, the behaviour is undefined.