CODEWITHSUNDEEP
javafor-loopwhile-loopbinary-search
red bean
red bean

Reputation: 3

where is my index out of bounds error happening?

having trouble writing my first binary search method.

public static int binarySearch(int [] a, int b){
    int mid = a[a.length-1]-a[0]/2;
    int high = a[a.length-1];
    int low = a[0];
    int found = -2;

    while (high > low){
      for (int i = high; i >= mid; i--){
        if (a[i] == b){
          found = i;
        }
      }
      for (int x = 0; x <= mid; x++){
        if (a[x] == b){
          found = x;
        }
      }
      if (a[mid] < b){
        low = mid;
        mid = high-low/2;
      } else if (a[mid] > b){
        high = mid;
        mid = high-low/2;
      } else if (a[mid] == b){
        found = mid;
      }
    }
  return found;
  }

I get an Index Out of Bounds error just at my call statement in my runner. I've been messing with the for-loops for awhile, but I'm not even sure that's what's the matter.

Upvotes: 0

Views: 64

Answers (2)

Amir MB
Amir MB

Reputation: 3418

Your binarySearch method is not correct. low, high and mid variables are supposed to be indexes of the array, not the actual values. The following is a simple implementation of it.

 public static int binarySearch(int [] a, int b){
    int mid;
    int high = a.length-1;
    int low = 0;

    while (high > low){
        mid = (low + high) / 2;
        if (a[mid] > b) 
            high = mid - 1;
        else if (a[mid] < b) 
            low = mid + 1;
        else 
            return mid;
    }
    return -2; // not found the key
}

Upvotes: 0

magikarp
magikarp

Reputation: 470

Consider the case:
a = [100, 200, 300, 400, 500]
b = 200

In your code, int mid = a[a.length-1]-a[0]/2; would assign mid the value as 500-100/2 = 450.

I can see that at multiple places in your code ahead, you're using a[mid] which means you're asking to fetch the element of a at the index 450. However, your array only has 5 elements.

Basically, you're working with values in the array when you should be working with the indices.

Upvotes: 1

Related Questions