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