Logical right shift in binary search preventing arithmetic overflow
algorithm, c, search
Solution
There is no such thing as a "logical right shift" in C (there's no `>>>` operator), so you're probably talking about Java.
This works because `low` and `high` are presumed to be in the range 0 to 2^31-1 (assuming we're talking about `int` here). The maximum possible value of `low+high` is no greater than than `2^32-2`, and so is representable by an `unsigned int` (if such a thing existed in Java). Such a thing doesn't exist in Java, so we've now overflowed. However, the logical shift operator `>>>` treats its operand as if it were unsigned, so this gives the expected result.
Problem
In a binary search implementation, obviously: ``` mid = (low + high)/2 ``` can cause overflow. I have read a lot of documentation (like this) that the following prevents the problem: ``` mid = (low + high) >>> 1 ``` However, I did not see a reason why this would work. Can anyone throw some light on this?