0

I'm trying to implement a recursive binary search, after looking at the example on this textbook page.

My algorithm seems to work fine in most cases, but on values higher than the highest value in the array, I get an ArrayIndexOutOfBoundsException. Looking at my algorithm and the textbook example, they seem identical; can someone help me find where I've gone wrong?

I'm aware this is mostly the same issue as in this thread, and I have already considered the solution it proposes. The example code however, does not implement any argument correction like this, and I wonder why it works without it.

    public static int binarySearch(int[] array, int item, int lowPos, int highPos){
    if (lowPos > highPos){
        return -1;
    }

    int mid = (lowPos + highPos)/2;

    if (array[mid] == item){
        return mid;
    }else if (array[mid] > item){
        return binarySearch(array, item, lowPos, mid-1);
    }else{
        return binarySearch(array, item, mid+1, highPos);
    }
}

This is the textbook example, which obviously does not produce the error:

    static int binarySearch(int[] A, int loIndex, int hiIndex, int value) {

   if (loIndex > hiIndex) {
         // The starting position comes after the final index,
         // so there are actually no elements in the specified
         // range.  The value does not occur in this empty list!
      return -1;
   }

   else {
         // Look at the middle position in the list.  If the
         // value occurs at that position, return that position.
         // Otherwise, search recursively in either the first
         // half or the second half of the list.
      int middle = (loIndex + hiIndex) / 2;
      if (value == A[middle])
         return middle;
      else if (value < A[middle])
         return binarySearch(A, loIndex, middle - 1, value);
      else   // value must be > A[middle]
         return binarySearch(A, middle + 1, hiIndex, value);
   }

} // end binarySearch()
5
  • What exception do you get? Can you post the stacktrace? Commented Jun 6, 2013 at 16:32
  • @LuiggiMendoza He says he gets an out of bounds exception. Commented Jun 6, 2013 at 16:33
  • Cannot replicate the behavior. Could you post the error-inducing code (too lazy too try to go through it)? I am thinking you might have put the wrong arguments there. Commented Jun 6, 2013 at 16:34
  • The only thing I can get is that you're sending the parameters in the wrong way. Note that book method uses array, low index, high index and value, while your method uses array, value, low index, high index. This means, when calling the binarySearch method from your client class/method e.g. public static void main(String[] args). Commented Jun 6, 2013 at 16:37
  • OP, would you please put us out our misery and let us know who is right? ;) Commented Jun 6, 2013 at 16:44

2 Answers 2

2

Your code is fine, you are just passing in values incorrectly. You are probably using the wrong highPos to start your method, if that is the case use myArray.length -1 as opposed to myArray.length.

Otherwise you are calling the arguments completely wrong for your revised method, possibly switching the values. The calling code should look like the following.

binarySearch(myArray, myIntToSearchFor, 0, myArray.length-1)
Sign up to request clarification or add additional context in comments.

8 Comments

That is most likely the issue. However, are you looking through a magic glass since I don't see the calling code posted (or maybe "you might be passing")? If you are right, kudos for random guessing.
The code is correct, so process of elimination
I don't think so. Refer to my last comment on OP's question. By the way, I wonder how did you eliminate something that you never saw before :).
But he properly switches how he calls the method to account for that. So that is not the issue. The code is good, his calling of the method is not
You're right, that is the other possible explanation, so I revised my answer to reflect that. But the issue is definitely is how he is calling the method, not the method code itself.
|
1

I believe you are passing array.length instead of array.length - 1 as the argument to highPos.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.