Binary search for integers I've written binary search with only my own efforts  without glancing at anywhere. I stuck on finding base case. At final, I think that if last checking is less than first index or first checking is greater than last index, it stops.  But, I'm still  suspicious of its performance and righness. I could return Integer.MAX_VALUE or Integer.MIN_VALUE if the searched number is not in the array but I assumed that all numbers are positive.

In the beginning times of writing recursion, I had difficulty in thinking recursively. But, now I have difficulty in finding base case(s).

public static int binarySearch(int[] arr, int key, int low, int high) {
        if (high &lt; 0 || low &gt; high )
            return -1;

        int middleIndex = (low + high) / 2;

        if (arr[middleIndex] == key)
            return middleIndex;
        else if (key &gt; arr[middleIndex])
            return binarySearch(arr, key, middleIndex + 1, high);
        else
            return binarySearch(arr, key, low, middleIndex - 1);

}
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.