7
\$\begingroup\$

I want to do binary search and if the target is not there get the index of where it should have been.

This is the code I came up with. It seems correct. Is there any problem? Can it be improved?

private int binarySearch(String[] sortedArray, String target, int start, int end) {

  if(start <= end){
     int mid = (start + end)/2;
     if(sortedArray[mid].equals(target)){
         return mid;
     }
     else if (target.compareTo(sortedArray[mid]) < 0){
         return binarySearch(sortedArray, target, start, mid - 1);
     }
     else{
         return binarySearch(sortedArray, target, mid + 1, end);
     }
  }

  return start;
}
\$\endgroup\$
  • 5
    \$\begingroup\$ Is there a reason you don't use Arrays.binarySearch ? \$\endgroup\$ – barjak Jan 28 '12 at 19:12
5
\$\begingroup\$

2 minor things:

  1. Remove the unnecessary comparison. If

    sortedArray[mid].equals(target)
    

    fails, it will again compare the two strings in the next if condition. Instead, you can just do:

    int c = target.compareTo(sortedArray[mid]);
    if(c == 0)
      return mid;
    else if(c < 0)
      ...
    
  2. To keep the method signature simple, you can overload it and delegate to the one that does the work:

    public int binarySearch(String[] sortedArray, String target) {
      binarySearch(sortedArray, target, 0, sortedArray.length - 1);
    }
    
\$\endgroup\$
5
\$\begingroup\$

One minor thing in addition to the other answers, there's a bug in your mid point calculation:

int mid = (start + end)/2;

it fails if the sum of low and high is greater than the maximum positive int value (2^31 - 1). The sum overflows to a negative value, and the value stays negative when divided by two. In C this causes an array index out of bounds with unpredictable results. In Java, it throws ArrayIndexOutOfBoundsException.

from Nearly All Binary Searches and Mergesorts are Broken

To prevent it from flowing over maximum int range replace it with:

int mid = low + ((high - low) / 2);

A very minor thing, that will only occur on arrays with a very high number of items. But since you asked for improvements of your code ...

\$\endgroup\$
2
\$\begingroup\$

Return start is incorrect. That will only happen if the target is not in the array, so you'll just end up with effectively a random index. Instead, I would use the Iterator pattern to return an Iterator to the target within the array instead of its index. That way you can handle the "not found" case as well.

Another simpler approach to this would be to just return -1, but then the client has to check against a "magic number", which is generally not a good thing.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the reply.Not sure I follow why return of start is incorrect.If the target is missing, I think that start would return the position it would have occupied.Do you think it does not achieve this? \$\endgroup\$ – user384706 Jan 28 '12 at 17:04
  • \$\begingroup\$ user384706: That is perhaps true, but it's confusing from a usability point of view, since you have to check twice to see if you actually found the result. That is, you'd have to say "int pos = binarySearch(array, word); if(array[pos] == word) { ... }". Additionally, that position would only be true if the array was not modified after the search, so it will quickly become meaningless. \$\endgroup\$ – mindvirus Jan 28 '12 at 17:31
  • \$\begingroup\$ @user384706 The standard solution for the absent element is to return the bitwise complement of the insertion position like here. The bitwise complement is always negative and usually written as -pos-1 instead of ~pos. \$\endgroup\$ – maaartinus Jun 15 '14 at 20:45
1
\$\begingroup\$

minor improvement, to seand's answer

private int binarySearch(String[] sortedArray, String target) {
    binarySearch(sortedArray, target, 0, sortedArray.length - 1);
}

private int binarySearch(String[] sortedArray, String target, int start, int end) {
    if (start > end)
        return start;
    int mid = (start + end) / 2;
    int c = target.compareTo(sortedArray[mid]);
    return (c == 0) ? mid : (c < 0) ?
            binarySearch(sortedArray, target, start, mid - 1) :
            binarySearch(sortedArray, target, mid + 1, end);
}
\$\endgroup\$
1
\$\begingroup\$

You have a recursive implementation, and Java isn't a functional language. If the input is too long, you might simply hit a java.lang.StackOverflowError.

Binary search can simply be written with imperative style, see Arrays.binarySearch.

\$\endgroup\$
  • \$\begingroup\$ This is correct in common. However, in the case of binary search the stack grows with ˋlog(array-size)ˋ. That should not be a problem even when the array has the maximum possible size. \$\endgroup\$ – aventurin Sep 30 '18 at 10:04

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.