I am looking for an efficient formula working in Java which calculates the following expression:
(low + high) / 2
which is used for binary search.
So far, I have been using "low + (high - low) / 2" and "high - (high - low) / 2"
to avoid overflow and underflows in some cases, but not both.
Now I am looking for an efficient way to do this, which would for for any integer (assuming integers range from -MAX_INT - 1 to MAX_INT).
UPDATE:
Combining the answers from Jander and Peter G. and experimenting a while I got the following formulas for middle value element and its immediate neighbors:
Lowest-midpoint (equal to floor((low + high)/2)
, e.g. [2 3] -> 2, [2 4] -> 3, [-3 -2] -> -3)
mid = (low & high) + ((low ^ high) >> 1);
Highest-midpoint (equal to ceil((low + high)/2)
, e.g. [2 3] -> 3, [2 4] -> 3, [-3 -2] -> -2)
low++;
mid = (low & high) + ((low ^ high) >> 1);
Before-midpoint (equal to floor((low + high - 1)/2))
, e.g. [2 3] -> 2, [2 4] -> 2, [-7 -3] -> -6)
high--;
mid = (low & high) + ((low ^ high) >> 1);
After-midpoint (equal to ceil((low + high + 1)/2))
, e.g. [2 3] -> 3, [2 4] -> 4, [-7 -3] -> -4)
mid = (low & high) + ((low ^ high) >> 1) + 1;
Or, without bitwise and (&) and or (|), slightly slower code (x >> 1
can be replaced with floor(x / 2)
to obtain bitwise operator free formulas):
Leftmost-midpoint
halfLow = (low >> 1), halfHigh = (high >> 1);
mid = halfLow + halfHigh + ((low-2*halfLow + high-2*halfHigh) >> 1);
Rightmost-midpoint
low++
halfLow = (low >> 1), halfHigh = (high >> 1);
mid = halfLow + halfHigh + ((low-2*halfLow + high-2*halfHigh) >> 1);
Before-midpoint
high--;
halfLow = (low >> 1), halfHigh = (high >> 1);
mid = halfLow + halfHigh + ((low-2*halfLow + high-2*halfHigh) >> 1);
After-midpoint
halfLow = (low >> 1), halfHigh = (high >> 1);
mid = halfLow + halfHigh + ((low-2*halfLow + high-2*halfHigh) >> 1) + 1;
Note: the above >>
operator is considered to be signed shift.
See Question&Answers more detail:
os