## Calculating mid in binary search

24

13

I was reading an algorithms book which had the following algorithm for binary search:

``````public class BinSearch {
static int search ( int [ ] A, int K ) {
int l = 0 ;
int u = A. length −1;
int m;
while (l <= u ) {
m = (l+u) /2;
if (A[m] < K) {
l = m + 1 ;
} else if (A[m] == K) {
return m;
} else {
u = m−1;
}
}
return −1;
}
}
``````

The author says "The error is in the assignment `m = (l+u)/2;` it can lead to overflow and should be replaced by `m = l + (u-l)/2`."

I can't see how that would cause an overflow. When I run the algorithm in my mind for a few different inputs, I don't see the mid's value going out of the array index.

So, in which cases would the overflow occur?

2adding, subtracting, multiplying 2 numbers all produce more bits, so obviously there's a chance of overflow – phuclv – 2016-01-28T05:30:56.443

Possible duplicate of binary search middle value calculation

– Jingguo Yao – 2017-01-03T06:12:47.383

34

This post covers this famous bug in a lot of detail. As others have said it's an overflow issue. The fix recommended on the link is as follows:

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

// Alternatively
int mid = (low + high) >>> 1;
``````

It is also probably worth mentioning that in case negative indices are allowed, or perhaps it's not even an array that's being searched (for example, searching for a value in some integer range satisfying some condition), the code above may not be correct as well. In this case, something as ugly as

``````(low < 0 && high > 0) ? (low + high) / 2 : low + (high - low) / 2
``````

may be necessary. One good example is searching for the median in an unsorted array without modifying it or using additional space by simply performing a binary search on the whole `Integer.MIN_VALUE``Integer.MAX_VALUE` range.

2+1 for the interesting link. – Randy Howard – 2014-08-30T14:07:54.297

The link you provided has a clear explanation of the issue. Thanks! – Bharat – 2011-07-18T16:20:47.713

3

The problem is that `(l+u)` is evaluated first, and could overflow int, so `(l+u)/2` would return the wrong value.

2

The potential overflow is in the `l+u` addition itself.