Binary search for integers
I don't immediately see something wrong with your base case. Perhaps it could be simplified, checking only for low &gt; high. You would need to think about what happens if you pass Integer.MAX_VALUE as high then though.

That being said, the implementation contains a major bug. low + high will overflow when the sum of them is greater than Integer.MAX_VALUE. You can use some mathematical tricks to solve this. Or use some bitwise operations, like (low + high) &gt;&gt;&gt; 1. 

The bitshift solution works for positive low and high (which they are). Although the sum can indeed still overflow, the unsigned shift operator &gt;&gt;&gt; shifts a zero in the most significant side. Mathematically, you could think of it as dividing the number interpreted as unsigned by two. As an example:

0111 1111 1111 1111 1111 1111 1111 1111 = Integer.MAX_VALUE 
0111 1111 1111 1111 1111 1111 1111 1111 = Integer.MAX_VALUE
--------------------------------------- +
1111 1111 1111 1111 1111 1111 1111 1110 = -2 ((2^32)-2 if interpreted as unsigned)


This sum overflows. Now, the difference between division (which would be the same as signed shift &gt;&gt;) and unsigned shift:

(-2) / 2   = 1111 1111 1111 1111 1111 1111 1111 1111 = -1
(-2) &gt;&gt;&gt; 2 = 0111 1111 1111 1111 1111 1111 1111 1111 = Integer.MAX_VALUE


Also note that the recursive calls may lead to a stack overflow in Java. Although it is a tail recursive implementation, this is not optimized in Java. So for a real world implementation, prefer iteration.

Final note: always try to use braces with if/else blocks.