The problem is the precedence of the operators.
The order for the 3 you use is as follows:
- Multiplicative
- Additive
- Shift
What happens, is that left+(right-left)>>1
is treated as if it were (left+(right-left))>>1
, which is not equal, but rather just right >> 1
or right / 2
.
You can see precedence here: http://docs.oracle.com/javase/tutorial/java/nutsandbolts/operators.html