0
\$\begingroup\$

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);

}
\$\endgroup\$
  • \$\begingroup\$ If you added javadocs, you could have added that the int arr[] has to be sorted ;) \$\endgroup\$ – RobAu May 16 '18 at 14:16
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ could you explain how (low + high) >>> 1 works? What if (low + high) overflows? \$\endgroup\$ – itsnotmyrealname May 16 '18 at 8:31
  • \$\begingroup\$ @itsnotmyrealname I updated the answer, does it clear up why it works? \$\endgroup\$ – Koekje May 16 '18 at 10:24
0
\$\begingroup\$
  • 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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Did you answer this with a different language in mind? :D \$\endgroup\$ – Koekje May 15 '18 at 18:34
  • \$\begingroup\$ @Koekje what made you think so? Mentioning STL doesn't imply C++. STL shows how the algorithm should be written, regardless of the language. \$\endgroup\$ – vnp May 15 '18 at 18:41
  • 1
    \$\begingroup\$ Mentioning pointers, unsigned types (specifically saying it makes no sense to index with a signed type) :) \$\endgroup\$ – Koekje May 15 '18 at 18:58
  • 2
    \$\begingroup\$ Java arrays are indexed with int, and there is no size_t in Java ... \$\endgroup\$ – Martin R May 15 '18 at 20:43
  • \$\begingroup\$ @MartinR Shame on me. I misread the tag. \$\endgroup\$ – vnp May 15 '18 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.