Binary search for integers

Question

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 < 0 || low > high )
            return -1;

        int middleIndex = (low + high) / 2;

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

}

Answer 1

I don't immediately see something wrong with your base case. Perhaps it could be simplified, checking only for low > 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) >>> 1.

The bitshift solution works for positive low and high (which they are). Although the sum can indeed still overflow, the unsigned shift operator >>> 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 >>) and unsigned shift:

(-2) / 2   = 1111 1111 1111 1111 1111 1111 1111 1111 = -1
(-2) >>> 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.

Answer 2

• Computation of (high + low)/2 may overflow. Prefer low + (high - low)/2.

• int is a wrong type for an index. An array can be large enough to go beyond the range of int. The only type which guarantees to hold an index into an array is size_t.

  As a side note, in the context of binary search it makes no sense to index an array with a signed type. One perk benefit is elimination of high < 0 test.

• I strongly recommend to not use indices at all, but use pointers to the beginning and the end of the range being searched.

• The what to return in case of failure is a common problem. It is enough to say that stdlib implementation got it wrong. The very same problem also manifests when the array contains multiple elements matching the key: the routine returns pretty much randomly. Not a problem with integers, but definitely a problem with more complex data.

  An answer is to always return the exact lower bound, STL style: do not short circuit as soon as you found the key, but keep going until you find its leftmost occurrence. If the key is not there, the lower bound would represent the insertion point, that is were the key would be inserted keeping an array sorted.

• The recursive invocation

  binarySearch(arr, key, low, middleIndex - 1);
  

  suggests that the low..high range is inclusive. Most algorithms are expressed better on the semi-open range, that is, with high is just beyond the range. Notice that if the key is greater than everything in the array, its lower bound(see above) is just beyond the range.

---

It is also worth mentioning that binary search is not the best problem to exercise recursion. I strongly recommend to recognize that it in fact is a tail recursion, and to rewrite it iteratively.