Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 5 down vote favorite

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;
}
share|improve this question
2  
Is there a reason you don't use Arrays.binarySearch ? – barjak Jan 28 '12 at 19:12

3 Answers

up vote 4 down vote accepted

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);
}
share|improve this answer
up vote 3 down vote

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

share|improve this answer
up vote 1 down vote

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.

share|improve this answer
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? – user384706 Jan 28 '12 at 17:04
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. – mdkess Jan 28 '12 at 17:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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